Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
The test cases are generated such that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.
Input/Output Specifications
- Input: Two heads of linked lists
- Output: The intersection node or null
- Constraints:
- The number of nodes of listA is in the range [1, 3 * 10^4]
- The number of nodes of listB is in the range [1, 3 * 10^4]
- 1 <= Node.val <= 10^5
- intersectVal is 0 if listA and listB do not intersect
- intersectVal == listA[skipA + 1] == listB[skipB + 1] if listA and listB intersect
Examples
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5].
There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
Example 2:
Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Solutions
Approach 1: Two Pointers (Optimal)
This approach uses two pointers that traverse both lists. When one pointer reaches the end, it switches to the other list. This ensures both pointers travel the same total distance.
Algorithm:
- Initialize two pointers at the heads of both lists
- Move both pointers one step at a time
- When a pointer reaches the end, switch it to the other list
- The intersection point is where both pointers meet
- If both pointers become null simultaneously, there’s no intersection
Python:
def getIntersectionNode(headA, headB):
"""
Find intersection of two linked lists using two pointers
Time: O(m + n)
Space: O(1)
"""
if not headA or not headB:
return None
ptrA = headA
ptrB = headB
while ptrA != ptrB:
# When ptrA reaches end, switch to headB
ptrA = headB if ptrA is None else ptrA.next
# When ptrB reaches end, switch to headA
ptrB = headA if ptrB is None else ptrB.next
return ptrA
Java:
class Solution {
/**
* Find intersection of two linked lists using two pointers
* Time: O(m + n)
* Space: O(1)
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode ptrA = headA;
ListNode ptrB = headB;
while (ptrA != ptrB) {
// When ptrA reaches end, switch to headB
ptrA = (ptrA == null) ? headB : ptrA.next;
// When ptrB reaches end, switch to headA
ptrB = (ptrB == null) ? headA : ptrB.next;
}
return ptrA;
}
}
Go:
// getIntersectionNode - Find intersection of two linked lists using two pointers
// Time: O(m + n)
// Space: O(1)
func getIntersectionNode(headA *ListNode, headB *ListNode) *ListNode {
if headA == nil || headB == nil {
return nil
}
ptrA := headA
ptrB := headB
for ptrA != ptrB {
// When ptrA reaches end, switch to headB
if ptrA == nil {
ptrA = headB
} else {
ptrA = ptrA.Next
}
// When ptrB reaches end, switch to headA
if ptrB == nil {
ptrB = headA
} else {
ptrB = ptrB.Next
}
}
return ptrA
}
JavaScript:
/**
* Find intersection of two linked lists using two pointers
* Time: O(m + n)
* Space: O(1)
*/
function getIntersectionNode(headA, headB) {
if (headA === null || headB === null) {
return null;
}
let ptrA = headA;
let ptrB = headB;
while (ptrA !== ptrB) {
// When ptrA reaches end, switch to headB
ptrA = ptrA === null ? headB : ptrA.next;
// When ptrB reaches end, switch to headA
ptrB = ptrB === null ? headA : ptrB.next;
}
return ptrA;
}
C#:
public class Solution {
/// <summary>
/// Find intersection of two linked lists using two pointers
/// Time: O(m + n)
/// Space: O(1)
/// </summary>
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode ptrA = headA;
ListNode ptrB = headB;
while (ptrA != ptrB) {
// When ptrA reaches end, switch to headB
ptrA = ptrA == null ? headB : ptrA.next;
// When ptrB reaches end, switch to headA
ptrB = ptrB == null ? headA : ptrB.next;
}
return ptrA;
}
}
Approach 2: Hash Set (Extra Space)
This approach uses a hash set to store visited nodes from the first list, then checks the second list for any visited nodes.
Algorithm:
- Traverse the first list and add all nodes to a hash set
- Traverse the second list and check if any node is in the hash set
- Return the first node found in the hash set
- If no intersection is found, return null
Python:
def getIntersectionNodeHashSet(headA, headB):
"""
Find intersection using hash set
Time: O(m + n)
Space: O(m)
"""
visited = set()
current = headA
# Add all nodes from first list to set
while current:
visited.add(current)
current = current.next
# Check second list for intersection
current = headB
while current:
if current in visited:
return current
current = current.next
return None
Java:
class Solution {
/**
* Find intersection using hash set
* Time: O(m + n)
* Space: O(m)
*/
public ListNode getIntersectionNodeHashSet(ListNode headA, ListNode headB) {
Set<ListNode> visited = new HashSet<>();
ListNode current = headA;
// Add all nodes from first list to set
while (current != null) {
visited.add(current);
current = current.next;
}
// Check second list for intersection
current = headB;
while (current != null) {
if (visited.contains(current)) {
return current;
}
current = current.next;
}
return null;
}
}
Go:
// getIntersectionNodeHashSet - Find intersection using hash set
// Time: O(m + n)
// Space: O(m)
func getIntersectionNodeHashSet(headA *ListNode, headB *ListNode) *ListNode {
visited := make(map[*ListNode]bool)
current := headA
// Add all nodes from first list to set
for current != nil {
visited[current] = true
current = current.Next
}
// Check second list for intersection
current = headB
for current != nil {
if visited[current] {
return current
}
current = current.Next
}
return nil
}
JavaScript:
/**
* Find intersection using hash set
* Time: O(m + n)
* Space: O(m)
*/
function getIntersectionNodeHashSet(headA, headB) {
const visited = new Set();
let current = headA;
// Add all nodes from first list to set
while (current !== null) {
visited.add(current);
current = current.next;
}
// Check second list for intersection
current = headB;
while (current !== null) {
if (visited.has(current)) {
return current;
}
current = current.next;
}
return null;
}
C#:
public class Solution {
/// <summary>
/// Find intersection using hash set
/// Time: O(m + n)
/// Space: O(m)
/// </summary>
public ListNode GetIntersectionNodeHashSet(ListNode headA, ListNode headB) {
HashSet<ListNode> visited = new HashSet<ListNode>();
ListNode current = headA;
// Add all nodes from first list to set
while (current != null) {
visited.Add(current);
current = current.next;
}
// Check second list for intersection
current = headB;
while (current != null) {
if (visited.Contains(current)) {
return current;
}
current = current.next;
}
return null;
}
}
Key Insights
- Two-pointer technique: Both pointers travel the same total distance
- Length difference handling: Switching lists compensates for different lengths
- Mathematical insight: If lists intersect, pointers will meet at intersection
- No intersection case: Both pointers become null simultaneously
- Space optimization: Two-pointer approach uses O(1) space vs O(m) for hash set
Edge Cases
- No intersection between lists
- Lists intersect at the first node
- Lists intersect at the last node
- One list is empty
- Both lists are empty
- Lists have very different lengths
Test Cases
# Test case 1: Lists intersect
# List A: 4->1->8->4->5
# List B: 5->6->1->8->4->5
# Intersection at node with value 8
# Test case 2: No intersection
# List A: 2->6->4
# List B: 1->5
# Expected: None
# Test case 3: Intersection at first node
# List A: 1->2->3
# List B: 1->2->3 (same list)
# Expected: Node with value 1
Follow-up Questions
- How would you handle cycles in the lists?
- Can you solve this with O(1) space and O(1) time?
- How would you find all intersection points?
- What if the lists are doubly linked?
Common Mistakes
- Not handling the case where lists don’t intersect
- Incorrect pointer switching logic
- Not considering lists of different lengths
- Forgetting to handle empty lists
- Infinite loops when not properly checking for null
- Memory issues with hash set approach for large lists