Intersection of Linked List
Given 2 linked lists which merge at some point. Find the node at which the lists merge.

Question

Intersection of Linked List

Given 2 linked lists which merge at some point. Find the node at which the lists merge.

Accepted Answer

Parallel Traversal Approach

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

Space Complexity: O(1)Explanation:

O(1)

Since we only use constant space.

Time Complexity: O(n)Explanation:

O(N), where N is the maximum length of the linked list.

Since we have to traverse only the longer linked list, therefore, the time complexity is O(N).

Accepted Answer

First I suggested the brute force approach in which we check each element of the first linked list with each element of other linked list and then moved on to the better-optimized solution using linked list traversal based on the difference of lengths of both linked list.

Accepted Answer

Brute Force

For each node in the first list, traverse the entire second list
Check if any node in the second list coincides with the first list
- If it does, return that node’s data
- If it doesn’t, return -1

Space Complexity: O(1)Explanation:

O(1)

Since we only use constant space.

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where N and M are the lengths of the first and second linked lists respectively.

Since, for each element of the first list, we are traversing for the second list, therefore the time complexity is O(N * M)

Accepted Answer

Hashing Approach

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

Space Complexity: O(n)Explanation:

O(N) or O(M), where N and M are the lengths of the first and second linked lists respectively.

Since we are storing nodes in the hash set, depending on which list’s nodes you store in the hash set/map/dictionary.

Time Complexity: OtherExplanation:

O(N+M), where N and M are the lengths of the first and second linked lists respectively.

Since we are traversing on the first and second linked list separately.

Top American Express Software Developer interview questions & answers