Intersection of Two Linked Lists
Two singly linked lists live in one pool of nodes. Node i links to node next[i], and -1 ends a list. List A starts at node headA and list B at node headB. The nodes are stored in no particular order, so follow the links.
The two lists may run into each other: from some node on, they continue through the same nodes to the end. Return the index of the first node that is on both lists, or -1 if they share no node.
Function
- nextinteger-array
- the index of the node each node links to, or -1 for the last node of a list
- headAinteger
- the first node of list A
- headBinteger
- the first node of list B
- Returnsinteger
- the first node the two lists share, or -1
Constraints
2 ≤ n ≤ 104, wherenis the length ofnext.- Each
next[i]is-1or a node index from0ton-1. 0 ≤ headA, headB ≤ n-1andheadA ≠ headB.- Both lists end at
-1without visiting a node twice. There is no cycle. - Every node is on list A, on list B, or on both.
Examples
- Input
- next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
- Output
- 1
- Explanation
- A visits
3, 5, 1, 4, 0and B visits2, 1, 4, 0. From node1on they share every node, and no earlier node of A is on B, so the answer is1.
- Input
- next = [2, 3, 4, -1, -1]headA = 0headB = 1
- Output
- -1
- Explanation
- List A is
0, 2, 4and list B is1, 3. Both end at-1without touching a common node, so the answer is-1.
- Input
- next = [3, 2, 0, -1]headA = 1headB = 0
- Output
- 0
- Explanation
- List A is
1, 2, 0, 3and list B is0, 3. List B is the tail of list A, so the first shared node isheadBitself, node0.
Follow-up
Can you find the node in O(m + k) time with O(1) extra memory?
Hints
Open them one at a time. Each one gives away a little more.
A node has one
next. Once the two lists reach the same node, can they ever split again? What does that tell you about the shape of the two lists?If both lists had the same length, you could walk them side by side and stop when the two pointers stand on the same node. The trouble is the extra nodes at the start of the longer list. How could both pointers walk the same total distance?
Walk pointer
aalong list A and, when it steps off the end, restart it atheadB. Do the same forb, restarting atheadA. Stop whena == b. That node, or-1, is the answer.
Solution
A node has one next, so two lists that meet never split again. They form a Y, two private starts joined to a shared tail, and the answer is the joint. The starts can differ in length, so stepping both lists together misses the joint. Below, m and k are the lengths of A and B.
Check each node of A against all of B
Correct, but does not finish on the largest tests
Intuition
A pointer is a node index, and moving forward is node = next[node]. For each node a of A in order, walk all of B and compare each node with a. The first a that matches is the answer, because every earlier node of A already failed. It rescans B for every node of A: with 5000 nodes on each list and no shared node, that is 2.5 × 10^7 comparisons.
Algorithm
- Set
a = headA. - While
ais not-1, walkbfromheadBto-1. - If
b == aat any point, returna. - Otherwise move
a = next[a]and repeat. - If list A runs out, return
-1.
def getIntersectionNode(next, headA, headB):
a = headA
while a != -1:
# Is node a also on list B? Walk all of B to find out.
b = headB
while b != -1:
if a == b:
return a
b = next[b]
a = next[a]
return -1Mark the nodes of list B
Intuition
Answer "is this node on B?" once for every node: walk B and mark each node in a boolean array of size n. The node indexes are small integers, so an array does the job of a hash set. Then walk A from its head. The first marked node is on both lists, and it is the first such node because you walk A in order. In the first example B marks 2, 1, 4, 0, and the walk along A passes 3 and 5 before it stops on 1. Each list is walked once, so the time is O(m + k), at the price of n marks.
Algorithm
- Create
onB, an array ofnbooleans set to false. - Walk list B from
headBand setonB[node] = truefor each node. - Walk list A from
headA. Return the first node withonB[node]true. - If list A ends, return
-1.
def getIntersectionNode(next, headA, headB):
# Mark every node of list B.
on_b = [False] * len(next)
node = headB
while node != -1:
on_b[node] = True
node = next[node]
# The first marked node on list A is the meeting point.
node = headA
while node != -1:
if on_b[node]:
return node
node = next[node]
return -1Two pointers that switch lists
Intuition
Split each list at the joint: A is x private nodes then the c shared ones, and B is y private nodes then the same c. Pointer a walks A, steps onto -1, then restarts at headB, and reaches the joint for the second time after x + c + 1 + y moves. Pointer b walks B, then A, and arrives after y + c + 1 + x moves. The totals match. In the first example x = 2, y = 1 and c = 3, and both stand on node 1 after seven moves.
With no shared tail, both pointers stand on -1 after m + 1 + k moves (after m when m = k), and the loop returns -1. That common stop is why each pointer steps onto -1 before it switches. Each pointer moves at most m + k + 1 times, with two indexes of memory.
Algorithm
- Set
a = headAandb = headB. - While
a != b: moveatoheadBif it is-1, otherwise tonext[a]. - In the same round, move
btoheadAif it is-1, otherwise tonext[b]. - When the loop ends, return
a. It is the first shared node, or-1.
def getIntersectionNode(next, headA, headB):
a, b = headA, headB
# Each pointer walks its own list, then the other one. Both cover
# the same number of nodes, so they reach the meeting node together,
# or reach -1 together when there is none.
while a != b:
a = headB if a == -1 else next[a]
b = headA if b == -1 else next[b]
return a
Pitfalls and edge cases
- Switching from the last node straight to the other head, skipping the stop on
-1. When the lists share nothing, the pointers never hold the same value and the loop runs forever. - Restarting a pointer at its own head. Each pointer then laps its own list, and they meet only when the laps line up, which can take up to
(m + 1)·(k + 1)moves. - Treating array order as list order. Node
0is a head only ifheadAorheadBsays so, and neighbours in the array are not neighbours in a list. - In Lua and R, forgetting that arrays start at 1. Keep node indexes 0-based and read
next[node + 1].
Frequently asked questions3
How do you find where two linked lists intersect without extra memory?
Run two pointers. Each walks its own list and, after stepping off the end, continues from the head of the other list. Both walk the same total distance, so they reach the first shared node at the same moment, or the end together when there is none.
Can you find the intersection by comparing the lengths of the lists?
Yes. Count the nodes of both lists, move the pointer on the longer list ahead by the difference, then move both one step at a time until they are equal. This is also O(m + k) time and O(1) memory; the switching method gets the same alignment without the two counting passes.
What is the time complexity of finding the intersection of two linked lists?
The two pointer and length methods run in O(m + k) time with O(1) extra memory. Remembering one list in a set or a marks array is also linear but needs memory for that list. Comparing every pair of nodes takes O(m·k).
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def getIntersectionNode(next, headA, headB):
# Write code hereTest #1
Test #2
Test #3
Arguments
next = [-1, 4, 1, 5, 0, 1] headA = 3 headB = 2
Expected Output
1