### 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!

## Comments

## Post a Comment