Problem overview
You get the heads of two singly linked lists, headA and headB. The lists may merge into a shared tail: from some node on, both lists continue through the very same nodes. GetIntersectionNode returns that first shared node, or null if the lists never meet. There are no cycles, and the lists must keep their original structure.
In the first example, list A is 4, 1, 8, 4, 5 and list B is 5, 6, 1, 8, 4, 5. The two lists share the tail 8, 4, 5, so the answer is the node holding 8. Notice that both lists also contain a node with value 1, but those are two different nodes, so they are not an intersection. An intersection means the same node object, not equal values.
The follow-up asks for O(m + n) time with O(1) memory, where m and n are the list lengths.
Approach: align the ends, then walk together
A simple solution stores every node of A in a HashSet<ListNode> and then walks B until it finds a node in the set. That runs in linear time but uses O(m) memory.
The constant-memory idea comes from one observation: after the intersection point, both lists are identical, so the part after the intersection has the same length in both. Any difference in total length therefore comes from the nodes before the intersection. If you skip the extra nodes at the front of the longer list, the two pointers are the same distance from the end, and from the intersection point. Walk them forward in lockstep and they land on the shared node at the same moment. If there is no intersection, both reach null at the same moment, and null == null ends the loop with the right answer.
The steps are:
- Count the nodes of each list.
- Advance the pointer of the longer list by the difference in length.
- Advance both pointers one node at a time until they refer to the same node.
With A of length 5 and B of length 6, B's pointer skips 1 node and moves to the node holding 6. The pointers then visit the pairs (4, 6), (1, 1) and (8, 8), where the first number comes from A and the second from B. The two 1s are different nodes, so the loop continues. The 8s are the same node, so it stops there and returns it.
Step by step
- Measure both lists with a helper,
Size(head), givingsizeAandsizeB. You write the helper afterwards. - Create two walkers,
nAandnB, starting at the heads. - Compare the lengths. If
sizeA < sizeB, B is longer, so advancenBbysizeB - sizeAusing a second helper,MoveNode(node, k). Otherwise advancenAbysizeA - sizeB. When the lengths are equal the difference is 0 and nothing moves. MoveNode can't change which node the caller's variable refers to; it returns the node where it stopped, so assign the result back. - Walk together with
while (nA != nB), moving both to theirnext. - Return
nA. It is the shared node, ornullwhen the lists don't meet. - Write
Sizeas a private method: a counter, a loop whilehead != nullthat increments it and movesheadforward, and thenreturn count. - Write
MoveNodeas a private method: a loop whilek > 0that movesnodeforward and decrementsk, and thenreturn node.
The solution in C#
class Solution {
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
int sizeA = Size(headA);
int sizeB = Size(headB);
ListNode nA = headA;
ListNode nB = headB;
if (sizeA < sizeB) {
nB = MoveNode(nB, sizeB - sizeA);
} else {
nA = MoveNode(nA, sizeA - sizeB);
}
while (nA != nB) {
nA = nA.next;
nB = nB.next;
}
return nA;
}
private int Size(ListNode head) {
int count = 0;
while (head != null) {
count++;
head = head.next;
}
return count;
}
private ListNode MoveNode(ListNode node, int k) {
while (k > 0) {
node = node.next;
k--;
}
return node;
}
}
C# details worth knowing
!=compares references.ListNodeis a class that doesn't overload the operator, sonA != nBasks whether the two variables refer to different node objects. It does not compare the values inside. That is exactly what this problem needs.- Parameters are copies. In
Size, movingheadalong the list changes only the method's own copy of the reference. The caller'sheadAstays where it was. This is also whyMoveNodehas to return its result. privatehelpers. Members of a class are private unless you say otherwise, and marking helpersprivateexplicitly makes the intent clear. Method names in C# use PascalCase, likeGetIntersectionNode,SizeandMoveNode.- The lists are not modified. The code only reads
next, so both lists keep their structure, as the problem requires.
Complexity
Counting the lists costs m + n steps. Aligning the pointers costs at most |m - n|. The final walk covers at most the shorter length. All of these are bounded by m + n, so the time is O(m + n). The method keeps a few integers and two references, so the extra space is O(1).
Edge cases and common mistakes
- No intersection. After alignment both pointers reach
nulltogether, so the loop ends and returnsnull. For[2, 6, 4]and[1, 5]the answer isnull. - Equal values, different nodes. Two lists with the same values but no shared nodes also return
null. Never comparevalfields to decide whether the nodes are the same. - Intersection at a head. If the lists are the same list, the lengths match, nothing is skipped, and the first comparison already succeeds.
- Skipping the wrong list. Advancing the shorter list lets the pointers walk past each other, and the loop may never find a match or may run into
nulland throwNullReferenceException. - Forgetting to assign the result of
MoveNode. CallingMoveNode(nB, 1);alone leavesnBunchanged. - Changing the lists to find the answer. Reversing or cutting nodes would break the requirement to keep the original structure.
Testing
Results from running the solution:
- The first example, with a shared tail starting at 8, returns the shared node, which compares equal (
==) to the node the tails share. [2, 6, 4]and[1, 5]with nothing shared returnsnull.- Two separate lists
[1, 2]and[1, 2]returnnull.