Problem Overview

Given the head pointers of two singly linked lists, the objective is to locate the node where the two lists merge. The solution must identify the first common node shared by both lists. If no intersection exists, the function should return null. The constraints require O(1) auxiliary space and O(N+M) time complexity, without modifying the original list structures.

Algorithm Strategy: Pointer Synchronization

The optimal approach utilizes two iterators to traverse the lists. By alternating the traversal path, we can neutralize the difference in list lengths. Two pointers, travellerA and travellerB, start at the heads of list A and list B respectively.

Both pointers move forward one node at a time. When travellerA reaches the end of its list (null), it is redirected to the head of list B. Conversely, when travellerB reaches the end of its list, it switches to the head of list A. This ensures that both pointers traverse a combined distance equal to the sum of the lengths of both lists. Consequently, they will become equal either at the intersection node or at null simultaneously.

C++ Implementation

#include <iostream>

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

class Solution {
public:
    ListNode* detectIntersection(ListNode* headA, ListNode* headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }

        ListNode* ptrA = headA;
        ListNode* ptrB = headB;

        // Traverse until the pointers meet
        while (ptrA != ptrB) {
            // If ptrA reaches the end, switch to headB, otherwise move to next
            if (ptrA == nullptr) {
                ptrA = headB;
            } else {
                ptrA = ptrA->next;
            }

            // If ptrB reaches the end, switch to headA, otherwise move to next
            if (ptrB == nullptr) {
                ptrB = headA;
            } else {
                ptrB = ptrB->next;
            }
        }

        // Return the intersection node or nullptr
        return ptrA;
    }
};

// Main function for demonstration
int main() {
    // Shared tail: 8 -> 4 -> 5
    ListNode* shared1 = new ListNode(8);
    ListNode* shared2 = new ListNode(4);
    ListNode* shared3 = new ListNode(5);
    shared1->next = shared2;
    shared2->next = shared3;

    // List A: 4 -> 1 -> [8 -> 4 -> 5]
    ListNode* a1 = new ListNode(4);
    ListNode* a2 = new ListNode(1);
    a1->next = a2;
    a2->next = shared1;

    // List B: 5 -> 0 -> 1 -> [8 -> 4 -> 5]
    ListNode* b1 = new ListNode(5);
    ListNode* b2 = new ListNode(0);
    ListNode* b3 = new ListNode(1);
    b1->next = b2;
    b2->next = b3;
    b3->next = shared1;

    Solution solver;
    ListNode* intersection = solver.detectIntersection(a1, b1);

    if (intersection) {
        std::cout << "Intersection Node Value: " << intersection->data << std::endl;
    } else {
        std::cout << "No intersection detected." << std::endl;
    }

    // Cleanup omitted for brevity
    return 0;
}

Logic Explanation

The algorithm works because the total distance traveled by both pointers becomes identical. Let a be the unique length of list A before the intersection, b be the unique length of list B before the intersection, and c be the length of the shared intersection.

• Pointer A path: Traverses a + c, then switches and traverses b. Total = a + c + b.
• Pointer B path: Traverses b + c, then switches and traverses a. Total = b + c + a.

Since both totals are equal (a + b + c), the pointers will synchronize exactly when they both enter the shared section c. This logic holds true only if the intersection refers to the exact same node in memory (reference equality), not just nodes with equal values.

Complexity Analysis

Time Complexity: O(N + M), where N and M are the lengths of the two linked lists. In the worst case, each pointer traverses both lists entirely.

Space Complexity: O(1). The solution only uses two pointer variables for tracking position, regardless of the input size.