"Intersection of Two Linked Lists": The Elegant Two-Pointer Solution (Java)

Hello everyone! Today, we're tackling a popular linked list problem: "Intersection of Two Linked Lists" (LeetCode #160).

The challenge is to find the exact node where two singly linked lists merge or "intersect." While it might seem tricky due to varying list lengths, there's an incredibly clever and efficient two-pointer technique that solves this in linear time and constant space. Let's dive in!

---

Understanding the Problem:

You are given the heads of two singly linked lists, headA and headB. Your task is to return the node at which the two lists begin to intersect. If they never intersect, return null.

Important Notes:

• Intersection means the same node reference: It's not just about nodes having the same val. It means they point to the exact same memory location.

• No Cycles: The problem guarantees there are no cycles in the linked lists.

• Original Structure: The lists must remain unchanged after your function executes.

• Judge Inputs (intersectVal, skipA, skipB): These are for the custom judge to set up the linked list structure for testing; they are not passed as parameters to your getIntersectionNode function. You only receive headA and headB.

Example 1:

• Input: listA = [4, 1, 8, 4, 5], listB = [5, 6, 1, 8, 4, 5], intersectVal = 8

• Output: Intersected at node with value '8'

  • This means listA is 4 -> 1 -> (node 8) and listB is 5 -> 6 -> 1 -> (node 8). Both lists then share 8 -> 4 -> 5.

---

My Thought Process & Approach (The Two-Pointer Trick):

The main challenge here is that the two lists might have different lengths before they potentially merge. How do we ensure our pointers "meet" at the right spot if an intersection exists, regardless of the initial lengths?

The Clever Idea: Imagine two people walking along two paths. If those paths eventually merge and become a single path, and both people walk at the same speed, they will eventually meet on the common path. The trick is to ensure they cover the same total distance before they reach the potential intersection point.

Here's how it works with two pointers, ptr1 starting at headA and ptr2 starting at headB:

1. Initialization:

   • ptr1 = headA

   • ptr2 = headB

2. The Loop: We iterate as long as ptr1 != ptr2.

3. Pointer Movement & Redirection:

   • In each step, advance both pointers by one node:

     • ptr1 = ptr1.next

     • ptr2 = ptr2.next

   • The Magic Step:

     • If ptr1 becomes null (meaning it has reached the end of listA), redirect it to headB.

     • If ptr2 becomes null (meaning it has reached the end of listB), redirect it to headA.

Why does this work?

Let L_A be the length of list A, L_B be the length of list B, and L_C be the length of the common part (from intersection point to end).

• Path of ptr1:

  • ptr1 traverses listA (length L_A).

  • If ptr1 reaches the end (null), it jumps to headB.

  • It then traverses listB (length L_B).

  • Total distance covered by ptr1: L_A + L_B.

• Path of ptr2:

  • ptr2 traverses listB (length L_B).

  • If ptr2 reaches the end (null), it jumps to headA.

  • It then traverses listA (length L_A).

  • Total distance covered by ptr2: L_B + L_A.

Since both pointers will traverse the exact same total distance (L_A + L_B), they are guaranteed to "normalize" their starting positions relative to the intersection point.

• If an intersection exists: They will meet at the first common node.

• If no intersection exists: Both pointers will eventually become null simultaneously (after traversing L_A + L_B nodes), and the loop will terminate with ptr1 == ptr2 == null. In this case, ptr1 (or ptr2) will be null, which is the correct return value.

This elegant solution ensures that both pointers travel the same "effective" distance, allowing them to meet at the intersection or at null if no intersection exists.

---

Java Code Implementation:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode ptr1 = headA;
        ListNode ptr2 = headB;
        while(ptr1!=ptr2){
            if(ptr1!=null){
              ptr1 = ptr1.next;
            }
            else{
                ptr1 = headB;
            }
            if(ptr2 != null){
                ptr2 = ptr2.next;
            }
            else{
                ptr2 = headA;
            }
        }
        return ptr1;
    }
}

Time and Space Complexity Analysis:

• Time Complexity: O(M + N)

  • Where M is the length of listA and N is the length of listB.

  • In the worst case (e.g., no intersection, or intersection at the very end), each pointer traverses M nodes then N nodes (or N then M).

  • Thus, the total number of steps is proportional to the sum of the lengths of the two lists.

• Space Complexity: O(1)

  • The algorithm uses only a constant number of extra variables (two pointers: ptr1 and ptr2).

  • No auxiliary data structures are created whose size depends on the input list lengths. This makes it a highly efficient solution in terms of space.