Code Implementation

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a
      

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return nullptr;
        ListNode* a = headA;
        ListNode* b = headB;
        while (a != b) {
            a = a ? a->next : headB;
            b = b ? b->next : headA;
        }
        return a;
    }
};
      

// 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) {
        if (headA == null || headB == null) return null;
        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = (a != null) ? a.next : headB;
            b = (b != null) ? b.next : headA;
        }
        return a;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    if (!headA || !headB) return null;
    let a = headA, b = headB;
    while (a !== b) {
        a = a ? a.next : headB;
        b = b ? b.next : headA;
    }
    return a;
};
      

Problem Description

Given two singly linked lists, headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection, return null.

• Each list consists of nodes, and nodes are compared by reference (not by value). That is, two nodes are the same if and only if they are the exact same object in memory.
• The linked lists may or may not intersect.
• There are no cycles in either list.
• It is guaranteed that there are no cycles in either of the lists.
• Do not modify the original linked lists.
• Return null if there is no intersection.
• There is exactly one intersection node if the lists intersect.

Thought Process

At first glance, the problem seems to require checking every node in one list against every node in the other. However, this brute-force approach is inefficient. We are looking for a node that is shared (by reference) between both lists. Since the lists may be of different lengths, a naive approach would not be optimal.

We want to find an efficient way to "align" the lists so that we can compare nodes in a single pass. A key observation is that after the intersection point, the two lists share all subsequent nodes. If we can traverse the same number of nodes from the end for both lists, we will eventually reach the intersection point if it exists.

The challenge is to handle lists of different lengths without using extra space. We can use two pointers and make them traverse both lists in such a way that they will either meet at the intersection node or both reach the end (null) at the same time if there is no intersection.

Solution Approach

The most efficient solution uses two pointers to traverse the two lists. Here's how it works:

1. Initialize two pointers, a and b, at the heads of headA and headB respectively.
2. Advance both pointers by one node at a time.
3. If either pointer reaches the end of its list, redirect it to the head of the other list.
4. Continue traversing until the two pointers meet. If the lists intersect, the pointers will eventually point to the same node (the intersection). If not, both will reach null at the same time.

This approach works because:

• Both pointers traverse the same total number of nodes (length of list A + length of list B).
• If there's an intersection, both pointers will enter the shared tail at the same time after switching.
• If there's no intersection, both pointers will reach the end (null) simultaneously.

Example Walkthrough

Suppose we have the following lists:

    List A: 4 → 1
                 \
                  8 → 4 → 5
                 /
    List B:   5 → 6 → 1
  

• List A has nodes: 4, 1, 8, 4, 5
• List B has nodes: 5, 6, 1, 8, 4, 5
• The intersection is at node with value 8 (by reference, not just value).

Walkthrough:

1. Pointer a starts at 4, pointer b at 5.
2. Both move one step at a time: a=1, b=6; a=8, b=1; a=4, b=8; a=5, b=4; a=null, b=5.
3. When a reaches null, redirect to headB (a=5). When b reaches null, redirect to headA (b=4).
4. Continue: a=6, b=1; a=1, b=8; a=8, b=4; a=4, b=5; a=5, b=null; a=null, b=null.
5. At this point, both pointers are at the intersection node (8), so we return it.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(mn), where m and n are the lengths of the two lists. For each node in list A, traverse all nodes in list B.
  • Space Complexity: O(1), since no extra data structures are used.
• Optimized two-pointer approach:
  • Time Complexity: O(m + n), as each pointer traverses each list at most once.
  • Space Complexity: O(1), since only two pointers are used.

The optimized approach is much more efficient, especially for long lists.

Summary

To find the intersection node of two singly linked lists, we use two pointers traversing the lists, switching heads when reaching the end. This ensures both pointers cover equal distances and meet at the intersection node if it exists, or at null otherwise. This approach is elegant, efficient (O(m + n) time, O(1) space), and avoids the need for extra data structures or modifying the input lists.