Problem Description

You are given the heads of two singly linked lists, headA and headB. Your task is to find and return the node where these two linked lists intersect. If the two linked lists don't intersect at all, return null.

When two linked lists intersect, they share the same nodes from the intersection point onwards. This means that from the intersection node, both lists have the exact same nodes (not just the same values, but the actual same node objects in memory).

For example, if list A is [4, 1, 8, 4, 5] and list B is [5, 6, 1, 8, 4, 5], and they intersect at the node with value 8, then from that node onwards, both lists share the nodes [8, 4, 5].

Important constraints:

• The linked lists have no cycles
• You must preserve the original structure of both linked lists (don't modify them)
• The intersection is based on node reference, not node value

The solution uses a two-pointer technique. Two pointers a and b start at headA and headB respectively. They traverse their lists, and when pointer a reaches the end of list A, it continues from the head of list B. Similarly, when pointer b reaches the end of list B, it continues from the head of list A.

The key insight is that by switching lists when reaching the end, both pointers will traverse the same total distance. If there's an intersection, they'll meet at the intersection node. If there's no intersection, both pointers will eventually become null at the same time.

The algorithm works because:

• If lists intersect: Both pointers travel (length of unique part of A) + (length of unique part of B) + (length of common part) before meeting
• If lists don't intersect: Both pointers travel (length of A) + (length of B) and become null together

Intuition

The challenge is finding where two linked lists meet when we can only traverse forward and don't know their lengths beforehand. The key observation is that if two lists intersect, they share a common "tail" from the intersection point onwards.

Let's think about the structure: if list A has length m and list B has length n, and they intersect at some node, then:

• List A has some unique nodes before the intersection
• List B has some unique nodes before the intersection
• Both share the same nodes after the intersection

The naive approach would be to check every node in list A against every node in list B, but that's inefficient. Another approach might be to find the lengths first, then align the lists, but that requires multiple passes.

The brilliant insight comes from realizing that the difference in path lengths is what prevents two pointers from meeting at the intersection when traversing simultaneously. If we could somehow "neutralize" this length difference, the pointers would naturally meet at the intersection.

Here's the key idea: if we concatenate the traversal paths, we get:

• Pointer starting at A: travels through A then through B
• Pointer starting at B: travels through B then through A

Both pointers now travel the exact same total distance: length(A) + length(B). More importantly, they both travel through the same unique portions of each list before reaching any potential intersection point.

If the lists intersect:

• Pointer A travels: (A's unique part) + (common part) + (B's unique part) + (common part)
• Pointer B travels: (B's unique part) + (common part) + (A's unique part) + (common part)
• They meet after traveling (A's unique part) + (B's unique part) + (common part)

If the lists don't intersect:

• Both pointers travel the full length of both lists and reach null simultaneously

This elegant solution ensures both pointers synchronize naturally without explicitly calculating lengths or making multiple passes.

Solution Approach

The implementation uses a two-pointer technique where both pointers traverse the linked lists in a specific pattern to find the intersection point.

Algorithm Steps:

1. Initialize two pointers: Set pointer a to headA and pointer b to headB.

2. Traverse both lists simultaneously: Move both pointers forward one node at a time using a while loop that continues as long as a != b.

3. Handle list switching:

   • When pointer a reaches the end of its current list (a becomes None), redirect it to the head of the other list: a = headB
   • When pointer b reaches the end of its current list (b becomes None), redirect it to the head of the other list: b = headA
   • If the pointer hasn't reached the end yet, simply move to the next node: a = a.next or b = b.next

4. Detect intersection or termination:

   • The loop exits when a == b, which happens in two cases:
     • Both pointers meet at the intersection node (if lists intersect)
     • Both pointers become None at the same time (if lists don't intersect)

5. Return the result: Return pointer a (or b, since they're equal), which will be either the intersection node or None.

Implementation Details:

The concise implementation uses Python's ternary operator to handle the list switching:

a = a.next if a else headB
b = b.next if b else headA

This checks if the pointer exists (hasn't reached None). If it exists, move to the next node; otherwise, switch to the head of the other list.

Time and Space Complexity:

• Time Complexity: O(m + n) where m and n are the lengths of the two lists. Each pointer traverses at most m + n nodes.
• Space Complexity: O(1) as we only use two pointers regardless of input size.

The beauty of this solution lies in its simplicity - no need to calculate lengths, no need for hash tables, just two pointers that eventually synchronize at the intersection point or at None.

Example Walkthrough

Let's walk through a concrete example to see how the two-pointer technique finds the intersection.

Example Setup:

• List A: 1 → 2 → 3 → 4 → 5
• List B: 9 → 4 → 5
• These lists intersect at node 4 (the same node object, not just same value)

Visual Representation:

List A: 1 → 2 → 3 ↘
                    4 → 5 → null
List B:         9 ↗

Step-by-step Execution:

Initial State:

• Pointer a starts at node 1 (head of List A)
• Pointer b starts at node 9 (head of List B)

Iteration 1: a != b (1 != 9)

• a moves from 1 to 2
• b moves from 9 to 4

Iteration 2: a != b (2 != 4)

• a moves from 2 to 3
• b moves from 4 to 5

Iteration 3: a != b (3 != 5)

• a moves from 3 to 4
• b moves from 5 to null

Iteration 4: a != b (4 != null)

• a moves from 4 to 5
• b reaches end, switches to head of List A: b = 1

Iteration 5: a != b (5 != 1)

• a moves from 5 to null
• b moves from 1 to 2

Iteration 6: a != b (null != 2)

• a reaches end, switches to head of List B: a = 9
• b moves from 2 to 3

Iteration 7: a != b (9 != 3)

• a moves from 9 to 4
• b moves from 3 to 4

Iteration 8: a == b (both at node 4)

• Loop exits
• Return node 4 (the intersection point)

Path Analysis:

• Pointer a traveled: 1→2→3→4→5→null→9→4 (total: 7 steps to intersection)
• Pointer b traveled: 9→4→5→null→1→2→3→4 (total: 7 steps to intersection)

Both pointers traveled exactly the same distance before meeting at the intersection node! This demonstrates why the algorithm works: by switching lists when reaching the end, both pointers equalize their path lengths and naturally synchronize at the intersection point.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n), where m is the length of linked list A and n is the length of linked list B.

The algorithm uses two pointers that traverse both linked lists. In the worst case, each pointer will traverse its own list completely and then traverse the other list until they meet at the intersection point (or both become None if there's no intersection).

• Pointer a travels at most: length of list A + length of list B = m + n
• Pointer b travels at most: length of list B + length of list A = n + m

Since both pointers move one step at a time simultaneously, the total iterations is bounded by m + n.

Space Complexity: O(1)

The algorithm only uses two pointers (a and b) to traverse the linked lists, requiring constant extra space regardless of the input size. No additional data structures like hash tables or arrays are used.

Common Pitfalls

1. Infinite Loop When Both Lists Are Empty

One common pitfall occurs when both input lists are None (empty lists). In this case, both pointers start as None, and the condition pointer_a != pointer_b evaluates to False immediately, which correctly returns None. However, some developers might try to "optimize" by adding extra conditions that could break this edge case.

Incorrect attempt:

# Wrong: Adding unnecessary null checks that break the algorithm
def getIntersectionNode(self, headA, headB):
    if not headA or not headB:  # Unnecessary check
        return None
  
    pointer_a = headA
    pointer_b = headB
  
    # This could cause infinite loop if lists don't intersect
    while pointer_a != pointer_b:
        pointer_a = pointer_a.next if pointer_a.next else headB  # Wrong!
        pointer_b = pointer_b.next if pointer_b.next else headA  # Wrong!
  
    return pointer_a

Why it's wrong: Checking pointer_a.next instead of pointer_a means the pointers never become None. If the lists don't intersect, the pointers will keep cycling through both lists infinitely.

2. Misunderstanding the Switching Logic

Another pitfall is incorrectly implementing the list-switching mechanism, particularly confusing when to switch lists.

Incorrect attempt:

# Wrong: Switching at the wrong time
def getIntersectionNode(self, headA, headB):
    pointer_a = headA
    pointer_b = headB
  
    while pointer_a != pointer_b:
        if pointer_a.next is None:  # Checking next instead of current
            pointer_a = headB
        else:
            pointer_a = pointer_a.next
          
        if pointer_b.next is None:  # Checking next instead of current
            pointer_b = headA
        else:
            pointer_b = pointer_b.next
  
    return pointer_a

Why it's wrong: This checks if the next node is None rather than the current pointer. This causes the pointers to switch one step too early, breaking the distance synchronization that makes the algorithm work.

3. Modifying the Original Lists

Some might be tempted to mark visited nodes or modify the list structure to detect cycles or intersections.

Incorrect attempt:

# Wrong: Modifying the original list structure
def getIntersectionNode(self, headA, headB):
    # Marking visited nodes by changing their values
    visited_marker = float('inf')
  
    current = headA
    while current:
        original_val = current.val
        current.val = visited_marker  # Modifying the list!
        current = current.next
  
    # Check if any node in list B was visited
    current = headB
    intersection = None
    while current:
        if current.val == visited_marker:
            intersection = current
            break
        current = current.next
  
    # Restore original values (but this is still wrong!)
    # ...
  
    return intersection

Why it's wrong: This violates the constraint of preserving the original list structure. Even if you restore values afterward, this approach fails when multiple threads access the lists concurrently.

Correct Solution Reminder

The correct implementation maintains simplicity:

def getIntersectionNode(self, headA, headB):
    pointer_a = headA
    pointer_b = headB
  
    while pointer_a != pointer_b:
        # Switch to the other list's head when reaching None (not before!)
        pointer_a = pointer_a.next if pointer_a else headB
        pointer_b = pointer_b.next if pointer_b else headA
  
    return pointer_a

Key points to remember:

• Check the current pointer for None, not pointer.next
• Let both pointers become None naturally if there's no intersection
• Never modify the original list nodes
• Trust the algorithm's elegance - both pointers will synchronize after traversing the same total distance