Intersection of Two Linked Lists
Problem
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
- If the two linked lists have no intersection at all, return null.
- The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
Solution
Amazing Two Pointers Solution: O(n) time, O(1) space
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode a = headA, b = headB;
while (a != b) {
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a; //or b, anyway
}
}
Analysis
To prove above solution work, let's take headA = [1,2,3,4,5,6]
and headB = [7,8,9,5]
as example
Since headA
has two nodes more than headB
, b
will be set to headA
earlier
After two more steps, a
will be set to headB
and b
passed two nodes already
Therefore, we guarantee that a
and b
will meet exactly at the intersection
If there is no intersection, they will be initially both set to null
hence we will return null
at the end