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

Blog Post: 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:

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
set<ListNode *> nodes_in_A;

{
}
{
{
}
}
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!