Intersection of Two Linked Lists

Problem Statement

In this task, we are given the starting nodes (heads) of two singly linked lists, denoted as headA and headB. The goal is to determine if these two lists intersect at some point and, if they do, return the node at which they begin to intersect. If there is no intersection point, the function should return null.

Linked lists are linear data structures where each element, known as a node, contains a value and a reference to the next node in the sequence. The problem asserts that there are no cycles in either of the linked lists, meaning they don't loop back on themselves.

To clarify, intersection here implies that nodes from both lists start sharing the same node instances from a certain point onwards. Importantly, even if two nodes from each list have the same value, they may not necessarily be the intersection point unless they are literally the same node (i.e., they occupy the same space in memory).

The task's complexities are compounded by the expectation that the original structure of the linked lists must be preserved throughout the execution of the function. This means you cannot modify the lists to solve the problem, such as by changing pointers.

The challenge is made more approachable by additional information supplied by a "Custom Judge" for testing:

• intersectVal specifies the value expected at the intersection node, or 0 if there is no intersection.
• listA and listB are the sequences of the linked lists.
• skipA and skipB describe the number of nodes to skip from the start of each list to reach the intersection point, enabling the simulation of various list configurations to validate solutions robustly.

Examples

Example 1

Input:

intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

Output:

Intersected at '8'

Explanation:

The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

Example 2

Input:

intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

Output:

Intersected at '2'

Explanation:

The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3

Input:

intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

Output:

No intersection

Explanation:

From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Constraints

• The number of nodes of listA is in the m.
• The number of nodes of listB is in the n.
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• intersectVal is 0 if listA and listB do not intersect.
• intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Approach and Intuition

The intersection of two linked lists can be visualized and approached as follows:

1. Length Calculation:

   • First, traverse each list to determine their lengths. This will help in aligning them in the following steps.

2. Alignment for Intersection:

   • Calculate the length difference between the two lists. Start a pointer from the head of the longer list and move it forward by the difference in lengths.
   • This ensures that when you subsequently move through both lists step by step, the pointers will reach the end of the lists simultaneously if there's no intersection, or intersect at the same node if there is one.

3. Simultaneous Traversal:

   • With pointers adjusted for any length discrepancy, traverse both lists at the same pace. If they intersect, the pointers will become equal at the intersection node (not just having the same value, but actually being the same node).
   • If they completely traverse the lists without this happening, then return null indicating no intersection.

This solution strategy ensures that the problem is solved in an optimal time complexity of O(M+N) where M and N are the lengths of the two lists, respectively, with a constant space complexity since only a few pointers are used. This meets the challenge's demands effectively while respecting the constraints provided.

In summary, understanding pointer manipulation and leveraging the characteristics of linked lists regarding traversal and node comparison are crucial in efficiently determining the point of intersection, if any.

Solutions

class Solution {
public:
    ListNode* findIntersection(ListNode* startA, ListNode* startB) {
        ListNode* currentA = startA;
        ListNode* currentB = startB;
        while (currentA != currentB) {
            currentA = currentA == nullptr ? startB : currentA->next;
            currentB = currentB == nullptr ? startA : currentB->next;
        }
        return currentA;
    }
};