Intersection of Two Linked Lists

LeetCode 160: Intersection of Two Linked Lists Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses two pointers traversing the concatenated length of both lists to neutralize length differences and locate the intersection node in $O(m+n)$ time with $O(1)$ space.

The Intersection of Two Linked Lists problem asks us to identify the specific node where two singly linked lists merge. If the lists intersect, they form a Y-shape, sharing all nodes after the intersection point. If they do not intersect, we must return null. Importantly, the solution must retain the original structure of the lists, and the intersection is defined by reference (memory address), not by node value. This is a classic LeetCode 160 interview question that tests pointer manipulation skills.

Brute Force Approach for Intersection of Two Linked Lists

The naive approach involves checking every node in the first list against every node in the second list to see if they point to the same memory location.

1. Iterate through headA with a pointer ptrA.
2. For every node visited by ptrA, iterate through the entire list headB using ptrB.
3. Check if ptrA == ptrB (reference equality).
4. If a match is found, return that node.
5. If loops complete without a match, return null.

Pseudo-code:

for nodeA in listA:
    for nodeB in listB:
        if nodeA is nodeB:
            return nodeA
return null

Complexity Analysis: The time complexity is $O(m \times n)$, where $m$ and $n$ are the lengths of the two lists. For large inputs (up to $3 \times 10^4$ nodes each), this results in approximately $10^9$ operations, which is highly inefficient and may lead to a Time Limit Exceeded (TLE) error or simply fail the interview constraint of linear time complexity.

Algorithm Strategy: Linked List Manipulation Patterns

Using the Linked List - Intersection Detection strategy, we maintain two pointers initialized at the heads of the respective lists.

1. Initialization: Create two pointers, ptrA and ptrB, pointing to headA and headB.
2. Traversal Loop: Enter a loop that continues as long as ptrA is not equal to ptrB.
3. Pointer Movement & Switching:
   • Advance ptrA to ptrA.next. If ptrA becomes null, redirect it to headB.
   • Advance ptrB to ptrB.next. If ptrB becomes null, redirect it to headA.
4. Termination: The loop terminates when ptrA == ptrB.
   • Case 1 (Intersection): Both pointers point to the intersecting node.
   • Case 2 (No Intersection): Both pointers become null simultaneously (after one full swap cycle).
5. Return: Return either ptrA or ptrB (since they are equal).

Execution Flow

1. Start: ptrA points to the first node of List A; ptrB points to the first node of List B.
2. Compare: Check if ptrA and ptrB refer to the same object. If yes, return ptrA.
3. Advance:
   • Move ptrA forward. If ptrA was at the last node of List A, move it to the first node of List B.
   • Move ptrB forward. If ptrB was at the last node of List B, move it to the first node of List A.
4. Repeat: Continue this process.
   • If the lists intersect, the pointers will eventually align at the intersection node because the "head start" of the shorter list is canceled out by the length of the longer list during the second pass.
   • If the lists do not intersect, both pointers will traverse len(A) + len(B) nodes and reach null at the same time. The condition ptrA == ptrB (where both are null) satisfies the loop termination.
5. Output: Return the node found (or null).

Proof of Correctness

Let $L_A$ be the length of List A, $L_B$ be the length of List B, and $C$ be the length of the shared suffix (intersection).

• The non-shared part of A is $L_A - C$.
• The non-shared part of B is $L_B - C$.

When ptrA traverses A then B, it travels $(L_A - C)$ nodes (unique A), then $C$ nodes (shared), then switches to B and travels $(L_B - C)$ nodes (unique B) before reaching the intersection again. Total distance to intersection: $(L_A - C) + C + (L_B - C) = L_A + L_B - C$.

When ptrB traverses B then A, it travels $(L_B - C)$ nodes (unique B), then $C$ nodes (shared), then switches to A and travels $(L_A - C)$ nodes (unique A) before reaching the intersection again. Total distance to intersection: $(L_B - C) + C + (L_A - C) = L_A + L_B - C$.

Since the distance to the intersection is identical for both pointers, and they move at the same speed (1 node/step), they are guaranteed to meet at the intersection node. If no intersection exists ($C=0$), they both travel $L_A + L_B$ and meet at null.

Pattern Reuse Notes

The Linked List - Intersection Detection pattern and the two-pointer synchronization technique are applicable to other problems:

• LeetCode 599: Minimum Index Sum of Two Lists - While this problem typically involves arrays/strings and hashmaps, the conceptual subpattern of finding the "meeting point" or commonality between two linear structures is similar.
• Cycle Detection (LeetCode 141): The logic of pointers traversing at different relative speeds or distances to detect a structural property (intersection vs. cycle) shares the same underlying intuition of invariant-based traversal.

Reference Implementation

C++ Solution for LeetCode 160

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9class Solution {
10public:
11    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
12        // If either head is null, there is no intersection
13        if (!headA || !headB) return nullptr;
14
15        ListNode *ptrA = headA;
16        ListNode *ptrB = headB;
17
18        // Traverse until the pointers meet (either at the intersection node or at null)
19        while (ptrA != ptrB) {
20            // If ptrA reaches the end of listA, switch to headB
21            // Otherwise, move to the next node
22            ptrA = (ptrA == nullptr) ? headB : ptrA->next;
23
24            // If ptrB reaches the end of listB, switch to headA
25            // Otherwise, move to the next node
26            ptrB = (ptrB == nullptr) ? headA : ptrB->next;
27        }
28
29        // Return the intersection node or null
30        return ptrA;
31    }
32};

Java Solution for LeetCode 160

1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode(int x) {
7 *         val = x;
8 *         next = null;
9 *     }
10 * }
11 */
12public class Solution {
13    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
14        // Boundary check
15        if (headA == null || headB == null) return null;
16
17        ListNode ptrA = headA;
18        ListNode ptrB = headB;
19
20        // Continue until they collide or both hit null
21        while (ptrA != ptrB) {
22            // Switch tracks at the end of the list
23            ptrA = (ptrA == null) ? headB : ptrA.next;
24            ptrB = (ptrB == null) ? headA : ptrB.next;
25        }
26
27        return ptrA;
28    }
29}

Python Solution for LeetCode 160

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, x):
4#         self.val = x
5#         self.next = None
6
7class Solution:
8    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
9        if not headA or not headB:
10            return None
11        
12        ptrA = headA
13        ptrB = headB
14        
15        # Loop until pointers meet or both become None
16        while ptrA != ptrB:
17            # If ptrA reaches end of list A, redirect to head B
18            ptrA = ptrA.next if ptrA else headB
19            # If ptrB reaches end of list B, redirect to head A
20            ptrB = ptrB.next if ptrB else headA
21            
22        return ptrA