DAY 98 - Intersection of Two Linked Lists

Hello Guys! This side Nayan and welcome to day 98 and we are going to solve another linked list problem.

In this article, we'll explore an efficient solution for a common problem in linked lists: Intersection of Two Linked Lists.

Problem Statement: Intersection of Two Linked Lists

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 null.

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

Leetcode has a custom solution judge for this problem. I will not be including it here but this solution works for that as well. I am trying to convey the process and algorithm through this solution.

Example 1:

Input: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5].
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.

Understanding the Approach(Intuition)

Before delving into the code, let's understand the intuition behind the approach used in the solution.

• The core idea behind the approach is to account for the difference in lengths between the two linked lists. Since the intersection point occurs at the same position from the end of both lists, we need to ensure that we start traversing from the same relative position in both lists.

• Basically if we were to start from the same position we will encounter the intersect after some time if it exists but to start from the same position we must first overcome the difference in length before the intersection.

• This is because after the intersection there are both the same length.

• To achieve this, we code a helper function lenDifference that calculates the length difference between listA and listB.

• The code then moves the pointers headA and headB such that they start at the same relative position in both lists.

• Finally, the code iterates through both lists simultaneously until it finds the intersection point, or until both pointers reach the end of their respective lists.

Visual Walkthrough

Code

class Solution {
public:
    int lenDifference(ListNode* headA, ListNode* headB) {
        int lenA = 0;
        int lenB = 0;
        while (headA || headB) {
            if (headA) {
                lenA++;
                headA = headA->next;
            }
            if (headB) {
                lenB++;
                headB = headB->next;
            }
        }
        return lenA - lenB; // If the difference is positive, List A is bigger; otherwise, List B is bigger.
    }

    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        // Step 1: Get the length difference.
        int lenDiff = lenDifference(headA, headB);

        // Step 2: Make the starting index the same.
        if (lenDiff < 0) {
            while (lenDiff != 0) {
                lenDiff++;
                headB = headB->next;
            }
        } else {
            while (lenDiff != 0) {
                lenDiff--;
                headA = headA->next;
            }
        }

        // Step 3: Traverse both linked lists and find the intersection.
        while (headA != headB) {
            headA = headA->next;
            headB = headB->next;
        }

        return headA;
    }
};

Complexity Analysis

Let's analyze the time and space complexity of this code.

Time Complexity

• The code iterates through both linked lists once to calculate the length difference, and then once again to find the intersection point. In both cases, it visits each node once.

• Therefore, the time complexity is O(max(m, n)), where m and n are the lengths of the two linked lists.

Space Complexity

• The code uses a constant amount of additional space, regardless of the size of the input linked lists.

• Thus, the space complexity is O(1), indicating that it uses a fixed amount of memory.