Intersection of Two Linked Lists easy

Problem Statement

You are given the heads of two singly linked-lists headA and headB. Return the node at which the two lists intersect. If the two linked lists have no intersection at all, return nullptr.

For example, the following two linked lists begin to intersect at node c1:

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

Example 1

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,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, you need to traverse 2 nodes to reach the intersection node. From the head of B, you need to traverse 3 nodes to reach the intersection node.

Example 2

Input: intersectVal = 2, listA = [0,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, you need to traverse 3 nodes to reach the intersection node. From the head of B, you need to traverse 1 node to reach the intersection node.

Steps

1. Calculate Lengths: Traverse both linked lists to find their lengths.
2. Find the Difference: Determine the difference in lengths between the two lists.
3. Adjust Pointers: Move the pointer of the longer list forward by the difference in lengths.
4. Traverse Simultaneously: Traverse both lists simultaneously, comparing nodes until a match is found or the end of one list is reached.

Explanation

The solution utilizes the concept of two pointers. By first finding the difference in lengths of the two lists, we ensure that when we start traversing both lists simultaneously from adjusted starting points, they will reach the intersection point (if it exists) at the same time. If there's no intersection, both pointers will reach the end of their respective lists without finding a common node. This approach avoids the need for nested loops, which would lead to O(n*m) time complexity.

Code

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (headA == nullptr || headB == nullptr) return nullptr;

    // Calculate lengths of lists
    int lenA = 0, lenB = 0;
    ListNode *tempA = headA, *tempB = headB;
    while (tempA != nullptr) {
        lenA++;
        tempA = tempA->next;
    }
    while (tempB != nullptr) {
        lenB++;
        tempB = tempB->next;
    }

    // Adjust pointers
    tempA = headA;
    tempB = headB;
    if (lenA > lenB) {
        int diff = lenA - lenB;
        while (diff--) tempA = tempA->next;
    } else {
        int diff = lenB - lenA;
        while (diff--) tempB = tempB->next;
    }

    // Traverse simultaneously
    while (tempA != nullptr && tempB != nullptr) {
        if (tempA == tempB) return tempA;
        tempA = tempA->next;
        tempB = tempB->next;
    }

    return nullptr; // 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 variables.