How to Solve Intersection of Two Linked Lists on LeetCode
The Intersection of Two Linked Lists is a common LeetCode and technical interview question. It tests pointer manipulation and knowledge of cycle and intersection detection in linked lists.
Problem Statement
Given the heads of two singly linked lists, return the node at which the two lists intersect. If the two linked lists have no intersection, return null.
Example:
Input: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
Output: Reference of the node with value = 8
Why This Problem Matters for Interviews
This problem:
- Tests pointer handling and linked list fundamentals
- Demonstrates optimal time and space approaches
- Relates to cycle detection (Floyd’s algorithm)
Approaches to Intersection of Two Linked Lists
1. Hash Set
Store nodes of the first list in a set, then check nodes in the second.
Time Complexity: O(m + n)
Space Complexity: O(m)
def getIntersectionNode(headA, headB):
nodes = set()
while headA:
nodes.add(headA)
headA = headA.next
while headB:
if headB in nodes:
return headB
headB = headB.next
return None
2. Two-Pointer Technique (Optimal)
Move through both lists; when a pointer hits the end, switch to the other list's head.
Time Complexity: O(m + n)
Space Complexity: O(1)
def getIntersectionNode(headA, headB):
if not headA or not headB:
return None
pA, pB = headA, headB
while pA != pB:
pA = pA.next if pA else headB
pB = pB.next if pB else headA
return pA
Key Interview Talking Points
- How two-pointer technique synchronizes path lengths
- Hash set vs two-pointer space usage
- Handling no intersection (null output)
- Relation to linked list cycles
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Set | O(m + n) | O(m) |
| Two Pointers | O(m + n) | O(1) |
Pro Interview Tips
- Draw intersecting and non-intersecting list diagrams.
- Explain pointer redirection in detail.
- Practice with test cases