Problem overview
The method getIntersectionNode receives the heads of two singly linked lists, headA and headB. The lists may merge into one shared tail. If they do, the method returns the first node that belongs to both lists. If they never meet, it returns nil. The lists have no cycles, and they must keep their structure: the method reads them and changes nothing.
In the first example, list A is [4, 1, 8, 4, 5] and list B is [5, 6, 1, 8, 4, 5]. A has two nodes before the shared part and B has three. The shared part starts at the node holding 8, so that node is the answer. In the third example, [2, 6, 4] and [1, 5] never meet, so the answer is nil.
The intersection is about identity, not values. Two different nodes that both hold 8 don't count. The answer is a node that both lists reach through their next links.
Approach: cut the longer list down to size
The simple idea is to take each node of A and search B for it, which is O(m * n). Storing the nodes of A in a set brings the time down to O(m + n) but uses O(m) memory. The statement's follow-up asks for linear time with constant memory.
The key observation is that once two lists merge, they stay merged: everything after the meeting node is the same chain, with the same length for both lists. So the nodes after the intersection don't differ in count. Only the part before it does, and the longer list has extra nodes there.
If the longer list skips its extra nodes, both pointers are the same distance from the end. Moving them forward one node at a time, they reach the intersection in the same step. If there is no intersection, they both reach nil in the same step. In both cases the loop "stop when the pointers are the same object" finishes, and the pointer holds the answer.
In the first example, A has 5 nodes and B has 6, so B skips one node and starts at the node holding 6, while A starts at its head, 4. Stepping together, they visit (4, 6), then (1, 1), then (8, 8), and stop because both are the same node.
Step by step
- Measure both lists. A helper
sizereturns the number of nodes. The lesson uses it first and writes it afterwards:sizeAandsizeB. - Create two walkers
nAandnBstarting at the heads. They arevar, since they move. - Find the longer list. If
sizeA < sizeB, B is longer, so advancenBbysizeB - sizeAnodes using the second helper,moveNode. Otherwise advancenAbysizeA - sizeB. When the sizes are equal, the second branch advances by 0, which does nothing. - Assign the result back.
moveNodereturns the node it stopped on. It can't change which node the caller's variable refers to, so the result must be stored, as innB = moveNode(nB, ...). - Walk together while
nA !== nB, moving both one node with?.next. - Return
nA. It is the intersection node, ornilif the walkers ran off the ends together. - Write
size. Copy the parameter into avar node, count whilenode != nil, and return the count. - Write
moveNode. Copy both parameters into mutable locals, then advancenwhilek > 0, countingkdown.
The solution in Swift
class Solution {
func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
let sizeA = size(headA)
let 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
}
func size(_ head: ListNode?) -> Int {
var count = 0
var node = head
while node != nil {
count += 1
node = node?.next
}
return count
}
func moveNode(_ node: ListNode?, _ k: Int) -> ListNode? {
var n = node
var k = k
while k > 0 {
n = n?.next
k -= 1
}
return n
}
}
The Swift details that matter here:
!==compares identity.ListNodeis a class, sonA !== nBasks whether both variables refer to the very same object. It works on optionals too, and twonilvalues count as identical, which is how the loop ends when there is no intersection. WritingnA != nBwould not compile, becauseListNodedoesn't conform toEquatable.- Parameters are constants. A function can't change its own parameters in Swift. That's why
sizestarts withvar node = head, and whymoveNodedeclaresvar k = k. The new local variable shadows the parameter of the same name. - Optional chaining.
nA?.nextgives the next node whennAhas a value, andnilwhennAisnil. No!is needed, so the walk can safely step past the last node. - Methods call each other by name. Inside a class,
size(headA)meansself.size(headA). The helpers can be declared below the method that uses them.
Complexity
Let m and n be the lengths of the lists.
Time: O(m + n). Measuring takes m + n steps. The alignment skips at most the longer length. The final loop makes at most min(m, n) steps, since after alignment the walkers have at most that many nodes left.
Space: O(1). The code keeps a few integers and two references.
Edge cases and common mistakes
- No intersection. The walkers reach
niltogether after the alignment, and the method returnsnil. For[2, 6, 4]and[1, 5]the result isnil. - Equal values, different nodes. Two separate lists
[1, 2]and[1, 2]hold equal numbers but share no node. The method returnsnil, because it compares identity, notval. - Intersection at a head. If both heads are the same node, the sizes are equal, nothing is skipped, and the loop condition is false at once. The method returns that head.
- Lists of different length. The common mistake is to start both walkers at the heads. They then pass each other's positions at different times and never line up on the shared node.
- Modifying the lists. The statement requires the original structure afterwards. This solution only follows
nextlinks and never assigns to them. - Comparing with
val. Values can repeat before the intersection. Compare nodes, not numbers.
Testing
- A =
[4, 1]followed by the shared nodes[8, 4, 5], B =[5, 6, 1]followed by the same shared nodes: returns the node holding 8. - A =
[2, 6, 4], B =[1, 5], no shared nodes: returnsnil. - The same list passed as both arguments: returns its head.
- Two separate lists
[1, 2]and[1, 2]: returnsnil.
