Leetcode: 160. Intersection of Two Linked Lists (Hash Table)

Singly Linked Lists Intersection

Today, we'll discuss a common problem involving singly-linked lists in the realm of data structures and algorithms: finding the intersection point of two linked lists.

Problem Statement

Given the heads of two singly linked-lists headA and headB, we need to write a function that returns the node at which the two lists intersect. If the two linked lists have no intersection at all, the function should return null.

Approach

Our approach to solving this problem involves using a hash set (specifically, a std::set in C++) to keep track of the nodes we encounter while traversing the first linked list (headA). We then traverse the second linked list (headB), and if we encounter any node that is present in the hash set, we can conclude that this is the intersection point.

Let's analyze the complexity of our solution:

• Time Complexity: Let m be the number of nodes in headA and n be the number of nodes in headB. The construction of the hash set takes O(m) time, and the second traversal of headB also takes O(n) time. Thus, the overall time complexity is O(m + n).
• Space Complexity: We use a hash set to store O(m) nodes from headA. Therefore, the space complexity is also O(m).

Code Example

Below is the C++ code implementation of the solution:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        set<ListNode *> nodes_in_A;

        while(headA != nullptr)
        {
            nodes_in_A.insert(headA);
            headA = headA->next;
        }
        while (headB != nullptr)
        {
            if (nodes_in_A.find(headB) != nodes_in_A.end())
            {
                return headB;
            }
            headB = headB->next;
        }
        return nullptr;
        
    }
};

With this implementation, you can now easily find the intersection node of two singly linked-lists using the provided function getIntersectionNode().

I hope you found this blog post helpful in understanding the problem and its solution. Happy coding!