Algorithm-Day22-Intersection-of-Two-Linked-Lists-lc-160

Posted on In , Views:

🧩 Problem Description

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 linked lists must retain their original structure after the function returns.

Example:

1
2
3
4
Input:
A: 4 → 1 → 8 → 4 → 5
B: 5 → 6 → 1 → 8 → 4 → 5
Output: Reference to node with value 8

💡 Brute Force (Not Ideal)

  • Compare every node from headA with every node from headB.
  • Time: O(m × n)
  • ❌ Inefficient

💡 Optimal Approach: Two Pointers

✨ Key Idea

  • Use two pointers pA and pB.
  • Traverse both lists:
    • If pA reaches end, redirect it to headB.
    • If pB reaches end, redirect it to headA.
  • They will either meet at the intersection node or both become null (no intersection).

Why it works:

  • Both pointers traverse exactly m + n steps.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode pA = headA;
        ListNode pB = headB;

        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }

        return pA;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(m + n)
  • Space Complexity: O(1)

✍️ Summary

  • This is a textbook two-pointer technique for linked lists.
  • Avoids using extra space like hash sets.
  • Useful for related problems such as:
    • lc-142: Linked List Cycle II
    • lc-21: Merge Two Sorted Lists

Pointer redirection is a simple yet powerful technique when dealing with linked lists of unequal lengths.