Leetcode 160 | Intersection Of Two Linked Lists in C++ | Singly Linked List | Hash Set | Two Pointers

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:

Courtesy of Leetcode.com

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Example:

Courtesy of Leetcode.com

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.

Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?

Approach

Implement a hash set-based approach to find the intersection of two linked lists.

First check if either of the input linked lists — headA or headB is nullptr. If so, return nullptr as there can be no intersection.

Next, use an unordered_set to store all nodes from the first linked list — headA.

Then iterate through the second linked list, headB and check if any node exists in the set. If a match is found, return the node as the intersection point.

If no intersection is found after traversing both lists, return nullptr as no intersection was found.

This approach is straightforward, but uses additional memory proportional to the size of the first linked list.

Code

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return nullptr;

        unordered_set<ListNode*> setA;
        ListNode* a = headA;
        while (a)
        {
            setA.insert(a);
            a = a->next;
        }

        ListNode* b = headB;
        while (b)
        {
            if (setA.find(b) != setA.end())
            {
                return b;
            }
            b = b->next;
        }

        // no intersection is found
        return nullptr;
    }

};

Optimal Approach

In this section, an optimal solution to the problem of finding he intersection node of two singly linked lists is presented.

The key idea behind this solution is to use two pointers, a and b, which traverse the two linked lists. Initially, a points to headA, and b points to headB. The while loop continues until a and b point to the same node (the intersection node) or both become nullptr (indicating no intersection).

Inside the loop, the pointers are advanced to the next node in their respective lists. However, when a pointer reaches the end of its list, it is redirected to the head of the other list. This ensures that both pointers traverse the same total number of nodes, regardless of the length of the two lists. By the time they meet, they will either both point to the intersection node or both be nullptr.

This approach works because redirecting the pointers effectively equalizes the lengths of the two traversals. If the lists intersect, the pointers will meet at the intersection node after traversing the same number of steps. If the lists do not intersect, both pointers will eventually reach the end of their respective lists and become nullptr at the same time, causing the loop to terminate.

a is returned (but b could also be returned), which will either be the intersection node or nullptr.

Code

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return nullptr;

        ListNode* a = headA;
        ListNode* b = headB;

        while (a != b)
        {
            a = a ? a->next : headB;
            b = b ? b->next : headA;
        }

        return a;
    }

};

Complexity Analysis

The time complexity is O(N+M) since we iterate, in the worst case, the number of elements in both lists.

The space complexity is O(N) for the hash-set solution and O(1) for the optimal solution, as it uses only two additional pointers.

Video Explanation

[embed]