# Intersection of Linked List

Posted: 22 Jul, 2020

Difficulty: Easy

#### You are given two Singly Linked List of integers, which are merging at some node of a third linked list.

#### Your task is to find the data of the node at which merging starts. If there is no merging, return -1.

#### For example:-

```
The given Linked Lists, where a1, a2, c1 is the first linked list, b1, b2, b3, c1 is the second linked list, and c1, c2, c3 is the third linked list which are merging at node c1.
```

##### Input Format:

```
The input format contains three lines consisting of three singly-linked lists.
All three lines contain the elements of the singly linked list separated by a single space and terminated by -1.
So first linked list would contain
a1, a2, ...an, c1, -1.
Similarly, the second line would contain
b1,b2, ...bm, c1, -1.
The third line would contain
c2, c3, ....ck, -1.
```

##### Output format :

```
The only line of output contains data of the first merged node. If there is no merging output should contain -1.
You don't have to explicitly print by yourself. It has been taken care of.
```

##### Constraints :

```
0 <= N <= 10^5
0 <= M <= 10^5
0 <= K <= 10^5.
-10^9 <= data <= 10^9 and data != -1
Time Limit: 1 sec
```

Approach 1

Approach 2

- Traverse the first list and store the address/reference to each node in a hash set/map/dictionary.
- Then check every node in the second list:
- If the address of the node of the second list appears in the hash set/map/dictionary, then the node is the intersection node
- If we do not find any address of the second list node in the hash set/map/dictionary then return -1

Approach 3

- Calculate the length of both the lists, say len1 and len2
- Get the absolute difference of the lengths, diff = |len1 – len2|
- Now traverse the long list from the first node till ‘diff’ nodes so that from there onwards both the lists have equal number of nodes
- Then traverse both the lists in parallel and check whether a common node is reached (Note that getting a common node is done by comparing the address of the nodes, not the data)
- If yes, return that node’s data
- If no, return -1

SIMILAR PROBLEMS

# Insertion In Circular Linked List

Posted: 21 Apr, 2022

Difficulty: Easy

# Insertion In A Singly Linked List

Posted: 22 Apr, 2022

Difficulty: Easy

# Remove Loop

Posted: 22 Apr, 2022

Difficulty: Moderate

# Deletion In Doubly Linked List

Posted: 22 Apr, 2022

Difficulty: Easy

# Insertion In Doubly Linked List

Posted: 24 Apr, 2022

Difficulty: Easy