Problem overview
The function getIntersectionNode receives the heads of two singly linked lists, headA and headB. The lists may merge into one shared tail. It must return the first node that both lists share, or null when they never meet. The lists must keep their original structure, and the input has no cycles.
Take list A as 4 -> 1 -> 8 -> 4 -> 5 and list B as 5 -> 6 -> 1 -> 8 -> 4 -> 5, where the nodes from 8 onward are the same objects in both lists. The answer is the node holding 8. Both lists contain a node with value 1 before that point, but those are two different nodes, so they don't count. The question is about shared nodes, not equal values.
The statement asks for O(m + n) time and O(1) extra memory, where m and n are the list lengths.
Approach: align the lists by length
A simple solution puts every node of A in a set, then walks B until it finds a node in the set. That is linear in time but uses O(m) memory. Another solution compares every node of A with every node of B, which needs no extra memory but takes O(m * n) time.
The lesson uses a better observation. Once two lists merge, they stay merged, so the part after the intersection is identical in both and has the same length. If A has 2 nodes before the intersection and B has 3, B is simply one node longer in total. When you skip those extra nodes at the front of the longer list, both pointers have the same number of nodes left. Moving them forward one step at a time then makes them land on the intersection node at the same moment. If there is no intersection, they both fall off the end together, and both become null.
Step by step
- Measure both lists with a helper called
size. Their lengths decide how far the longer list must be advanced. - Create two walking pointers,
nAandnB, asvars starting at the heads. The parameters themselves can't be reassigned, and the walkers will move. - Find the longer list. If
sizeA < sizeB, advancenBbysizeB - sizeAnodes using a second helper,moveNode. Otherwise advancenAbysizeA - sizeB. When the lengths are equal the distance is 0 and nothing moves. - Walk in lockstep while
nA !== nB, advancing both pointers by one node each time. - Return
nA. The loop ends when the pointers refer to the same node, which is the intersection, or when both arenull, which means no intersection. - Write
size. Copy the parameter into avar, count nodes until it becomesnull, and return the count. - Write
moveNode. Copy both parameters into local variables, follownextktimes and return where you ended up.
The solution in Kotlin
class Solution {
fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
val sizeA = size(headA)
val sizeB = size(headB)
var nA = headA
var 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
}
fun size(head: ListNode?): Int {
var count = 0
var node = head
while (node != null) {
count++
node = node?.next
}
return count
}
fun moveNode(node: ListNode?, k: Int): ListNode? {
var n = node
var kk = k
while (kk > 0) {
n = n?.next
kk--
}
return n
}
}
The Kotlin details worth knowing:
!==is the key operator. In Kotlin,==callsequals, and!==compares references: it is true when the two variables point at different objects. Two different nodes can hold the same value, so the loop must compare identity. For an ordinary class that doesn't overrideequals,!=would also compare references, but!==says what you mean and survives a later change to the class.- Nullable types. A
ListNode?may benull, sonA?.nextis the safe call: it givesnullwhennAisnulland the next node otherwise. That lets both walkers step past the end without a crash. - Parameters are read-only. A Kotlin function parameter can't be reassigned, which is why
sizeandmoveNodefirst copy them intovar node,var nandvar kk. - The extra
?.insize. Insidewhile (node != null), Kotlin already knows the local variablenodeis not null, sonode.nextwould be enough. The?.is harmless, but the compiler may flag it as unnecessary. if/elsecovers equal lengths. With equal sizes theelsebranch runs and callsmoveNode(nA, 0), which returnsnAunchanged.
Complexity
Time: O(m + n). size visits every node of each list once. moveNode takes at most max(m, n) steps, and the final loop takes at most min(m, n) steps, since after alignment the shorter list's length bounds it. Each part is linear.
Space: O(1). Only a few integers and pointers are used, and nothing is stored per node. The lists aren't modified, which satisfies the requirement to keep their structure.
Edge cases and common mistakes
- No intersection. For A =
2 -> 6 -> 4and B =1 -> 5, B is advanced past nothing, A is advanced by 1 node, and the walkers step together until both arenull. The function returnsnull. - Equal values, different nodes. Two separate lists
1 -> 2and1 -> 2share no node, so the answer isnull. Comparingvalfields would wrongly report an intersection. - Intersection at a head. If both heads are the same node, the lengths match, nothing moves, and the loop doesn't run. The function returns that head.
- One list inside the other. If B is a suffix of A, B's head is the intersection. A is advanced until it reaches that node.
- Advancing the wrong list. The extra nodes belong to the longer list. Advancing the shorter one would make the pointers walk past each other, and they would never meet.
- Forgetting to assign the result.
moveNode(nB, d)doesn't changenB. It returns the node it stopped on, and that value has to be stored back.
Testing
- A =
4, 1, 8, 4, 5and B =5, 6, 1, 8, 4, 5sharing the tail from8: returns the node with value8. - A =
1, 9, 1, 2, 4and B =3, 2, 4sharing the tail from2: returns the node with value2. - A =
2, 6, 4and B =1, 5, nothing shared: returnsnull. - The same list passed as both arguments: returns its head.