#160
Intersection of Two Linked Lists
Easy Two pointers switching lists
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Two singly linked lists may merge at some node and share their tail. Return that first shared node, or null.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the first node shared by both lists.
Why this works: walk A then B, and B then A. Both pointers travel the same total distance, so they meet at the shared node (or at null).
Example: A: 4→1→8→4→5, B: 5→6→1→8→4→5 (shared from 8)
pointer A walks 5 + 3, pointer B walks 6 + 2 → both arrive at 8 together✦Hints open one at a time
If the lists had equal length, you'd walk them together.
When pointer A reaches the end, send it to the head of B, and vice versa.
↗Approach
Both pointers travel lenA + lenB steps in total, so they line up and meet at the intersection (or both reach null at the same time if there is none).
</>Solution (Java)
/**
* class ListNode { int val; ListNode next; } // provided by LeetCode
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) {
a = (a == null) ? headB : a.next; // switch lists at the end
b = (b == null) ? headA : b.next;
}
return a;
}
}!Common mistake
Comparing values instead of node references — different nodes can hold equal values.
Complexity
- Time: O(n + m).
- Space: O(1).
Topic: Linked List
🎬 Episodes 40–45: video coming soon