Intersection of Two Linked Lists easy

Problem Statement

Write a function to find the node at which two singly linked lists intersect. The lists are non-cyclical.

For example, the following two linked lists:

A: a1 → a2 ↘ c1 → c2 → c3 ↗
B: b1 → b2 → b3

begin to intersect at node c1.

Example 1

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 Output: Intersecting node's reference: 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.

Example 2

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Output: Intersecting node's reference: 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: null 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 don't intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values. The two lists do not intersect, so return null.

Steps

1. Traverse both lists to find their lengths: This helps us determine which list is longer.

2. Align the pointers: Start the pointer for the longer list skip nodes ahead, where skip is the difference in lengths between the two lists. This ensures that both pointers reach the intersection point (if it exists) simultaneously.

3. Simultaneous Traversal: Move both pointers one node at a time until they either meet (at the intersection point) or reach the end of a list (indicating no intersection).

Explanation

The core idea is to cleverly use the properties of linked lists. If two lists intersect, they share a common tail. By aligning the pointers and traversing simultaneously, we ensure that if an intersection exists, the pointers will eventually converge at that point. If no intersection exists, the pointers will reach the end of their respective lists without meeting.

Code

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
    }
}

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    if (!headA || !headB) return null;

    // Find lengths of lists
    let lenA = 0;
    let lenB = 0;
    let currA = headA;
    let currB = headB;
    while (currA) {
        lenA++;
        currA = currA.next;
    }
    while (currB) {
        lenB++;
        currB = currB.next;
    }

    // Align pointers
    currA = headA;
    currB = headB;
    let diff = Math.abs(lenA - lenB);
    if (lenA > lenB) {
        while (diff--) {
            currA = currA!.next;
        }
    } else {
        while (diff--) {
            currB = currB!.next;
        }
    }

    // Simultaneous traversal
    while (currA && currB) {
        if (currA === currB) return currA;
        currA = currA.next;
        currB = currB.next;
    }

    return null; // No intersection
}

Complexity

• Time Complexity: O(m + n), where m and n are the lengths of the two linked lists. We traverse each list once.
• Space Complexity: O(1). We use only a constant amount of extra space to store pointers and length variables.