Intersection of two linked lists

160.Intersection of Two Linked Lists

Linked List

Two Pointers

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.

Intuition:

The key insight is that if two pointers traverse both lists, they will meet at the intersection point. This works because: - If lists are different lengths, the pointers will swap to the other list's head - After swapping, they end up separated by exactly the length difference - This means they'll align at the intersection point - If there's no intersection, they'll both reach null simultaneously

Example:

Input:

listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]

→

Output:

Intersected at '8'

Complexity:

Time: O(N) | Space: O(1)

Java Solution:

// Clever solution using list length difference
// When pointers reach end of their lists, they switch to the other list
// This ensures they'll meet at intersection after traveling equal distances
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode p1 = headA;
    ListNode p2 = headB;
    
    // Loop until pointers meet or both reach null
    while (p1 != p2) {
        // Switch to other list when reaching end
        p1 = p1 == null ? headB : p1.next;
        p2 = p2 == null ? headA : p2.next;
    }
    
    // Will be intersection point or null if no intersection
    return p1;
    
    // Note: If lists don't intersect, pointers will still align
    // Both will reach null after traveling both lists
}

Python Solution:

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    # Handle edge cases
    if not headA or not headB:
        return None
        
    p1, p2 = headA, headB
    
    # Loop until meet or both reach end
    while p1 != p2:
        # Switch lists at end
        p1 = p1.next if p1 else headB
        p2 = p2.next if p2 else headA
        
    return p1

C++ Solution:

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if(!headA || !headB) return nullptr;
        
        ListNode *p1 = headA, *p2 = headB;
        
        // Loop until pointers align
        while(p1 != p2) {
            // Move to other list at end
            p1 = p1 ? p1->next : headB;
            p2 = p2 ? p2->next : headA;
        }
        
        return p1;
    }
};