Intersection of Two Linked Lists
- mosesg1123
- May 2
- 4 min read
Finding the intersection node of two linked lists is like spotting the shared checkpoint in two runners’ paths—useful for debugging shared resources or merging event streams. It’s a classic interview problem that tests pointer arithmetic, traversal strategies, and trade‐offs between time and space.
Problem Statement
Given the heads of two singly linked lists, return the node at which the two lists intersect. If the two lists have no intersection, return null. The lists must retain their original structure. Aim for O(n + m) time and O(1) extra space if possible.
// Definition provided in the interview:
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; next = null; }
}
// Signature:
public ListNode getIntersectionNode(ListNode headA, ListNode headB);
1. Clarify Requirements Before Jumping Into Code
I’ll confirm a few details:
If there is no intersection, return null.
Intersection means the same node reference, not merely same value.
Lists may be very different lengths.
I cannot modify the lists.
Extra space should be minimal; constant extra space is ideal.
2. Identify the Category of the Question
This is a linked list problem involving pointer alignment. Common patterns include:
Two-pointer traversal (fast/slow, parallel walkers)
Hash-based visited-node detection
Length calculation and offset adjustment
Cycle detection variants
Spotting intersection by reference, not value, hints at pointer-based solutions.
3. Consider a Brute‑Force Approach to Understand the Problem
A brute-force approach is nested loops:
for each node a in list A:
for each node b in list B:
if a == b:
return a
return null
Time: O(n·m)
Space: O(1)
Too slow for long lists but confirms correctness.
4. Brainstorm More Solutions
I need something faster:
Hash Set of nodes from A:Traverse A, store each node reference in a set. Then traverse B, returning the first node found in the set.
Time: O(n + m)
Space: O(n)
Cycle trick:Temporarily connect tail of A to head of B, then detect cycle start. This uses cycle detection but modifies the list (even if temporarily). Safer to use hashing or pointer alignment.
Two-pointer length alignment:Measure lengths of A and B (lenA, lenB). Advance the longer list’s pointer by |lenA - lenB| to align the tails. Then move both pointers one step at a time until they meet or both reach null.
Time: O(n + m)
Space: O(1)
To derive the two-pointer alignment on the fly, imagine lining up two runners at different start points so they finish at the same time. If one track is shorter, that runner starts further back. Then stepping together will reveal where their paths cross.
5. Discuss Trade‑Offs Between Your Solutions
Approach | Time | Space | Pros | Cons |
Hash Set | O(n + m) | O(n) | Very simple, single pass B detects | Extra O(n) memory |
Two-Pointer Alignment | O(n + m) | O(1) | Constant space, clear pointer logic | Requires length calculations |
Tail-to-Head Cycle Trick | O(n + m) | O(1) | Clever reuse of cycle detection | Modifies list structure briefly |
Two‑pointer alignment is optimal for time and space without destructive side effects.
6. Write Pseudocode to Structure Your Thoughts
function getIntersectionNode(headA, headB):
// 1. Compute lengths
lenA = length(headA)
lenB = length(headB)
// 2. Align starts
ptrA = headA
ptrB = headB
if lenA > lenB:
advance ptrA by (lenA - lenB)
else:
advance ptrB by (lenB - lenA)
// 3. Traverse together
while ptrA != null and ptrB != null:
if ptrA == ptrB:
return ptrA
ptrA = ptrA.next
ptrB = ptrB.next
return null
7. Consider Edge Cases
One or both heads are null → return null.
Lists with no intersection → return null.
Intersection at head → immediate match.
Intersection at tail → works after aligning.
One list much longer than the other → alignment handles offset correctly.
8. Write Full Code Syntax
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// Compute lengths
int lenA = getLength(headA);
int lenB = getLength(headB);
// Align starting pointers
ListNode ptrA = headA;
ListNode ptrB = headB;
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; i++) {
ptrA = ptrA.next;
}
} else {
for (int i = 0; i < lenB - lenA; i++) {
ptrB = ptrB.next;
}
}
// Traverse together
while (ptrA != null && ptrB != null) {
if (ptrA == ptrB) {
return ptrA;
}
ptrA = ptrA.next;
ptrB = ptrB.next;
}
return null;
}
private int getLength(ListNode head) {
int length = 0;
ListNode curr = head;
while (curr != null) {
length++;
curr = curr.next;
}
return length;
}
}
9. Test Your Code
public static void main(String[] args) {
Solution sol = new Solution();
// Helper: buildList(...) creates a new list; connectNodes(a, b) links b offset into a
// Test 1: no intersection
ListNode a1 = buildList(1,2,3);
ListNode b1 = buildList(4,5,6);
assert sol.getIntersectionNode(a1, b1) == null;
// Test 2: intersection at head
ListNode common = buildList(7,8,9);
ListNode a2 = common;
ListNode b2 = common;
assert sol.getIntersectionNode(a2, b2) == common;
// Test 3: intersection in middle
ListNode a3 = buildList(1,2);
a3.next.next = common; // 1->2->7...
ListNode b3 = buildList(3,4,5);
b3.next.next.next = common; // 3->4->5->7...
assert sol.getIntersectionNode(a3, b3) == common;
// Test 4: intersection at tail
ListNode tail = new ListNode(10);
ListNode a4 = buildList(1,2);
a4.next.next = tail;
ListNode b4 = buildList(3);
b4.next = tail;
assert sol.getIntersectionNode(a4, b4) == tail;
// Test 5: one list empty
assert sol.getIntersectionNode(null, buildList(1,2)) == null;
System.out.println("All tests passed!");
}
10. Key Lessons to Remember for Future Questions
Length alignment is a powerful two‐pointer tool when lists differ in size.
Always handle null heads and unequal lengths before pointer traversal.
Clear helper functions (e.g., getLength) keep main logic concise.
Testing head, middle, tail intersections, and no‐intersection covers full spectrum.
Discussing hash‐set versus pointer alignment shows awareness of space/time trade‑offs.
Visual analogies—lining runners at adjusted starts—help explain pointer moves under pressure.
Good Luck and Happy Coding!
Comments