Easy: Find the merge point between two lists.

Explanation:
List1  
15
 \     List2
  4    6
   \  /
    3
    |
    2
For List1 & List2, the merge-point is 3, Where these two lists referentially target to the same node.

Problem statement:

The task is to complete the function mergePoint() which takes the pointer to the head of linklist1 and linklist2, as input parameters and returns the data value of a node where two linked lists intersect. If the linked list does not merge at any point, then it should return -1.

Solution:

At this time, multiple solutions came into my mind

Solution 1: NotSoGood

1. Take one list(say list1) and copy its data into an array(say arr).
2. Take another list(list2) and increment the data of all nodes by 1.
3. Now, traverse through list1 and match it’s content with backup array(arr), if you find a node where data is not the same as a backup array, it’s the intersection point.
4. If the data of list1 is the same as its backup array which means there is no intersection point, and you should return -1.

Analysis: It changes the content of the list2, which is not desirable. Requires extra storage for the backup array.

Solution 2.

1. Convert both linked lists into doubly-linked lists.
2. Traverse from the tails of both lists to find out the intersection point.

List1  
15
 \\     List2
  4    6
   \\  //
     3
     ||
      2
(Tail1, Tail2)

Analysis: It changes the original lists, which is not desirable. Requires extra storage to store double pointers. However, the solution’s simple to understand and straightforward.

Solution 3: Better
Let’s try a better solution, without any extra storage requirements.

List1  
15
 \     List2
  4    6
   \  /
    3
    |
    2

1. Get count of the nodes in the first list, let be c1.
2. Get count of the nodes in the second list, let be c2.
3. Get the difference of counts d = abs(c1 — c2)
4. Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5. Then we can traverse both the lists in parallel till we come across a common node.

Run this code over here: leetcode.com/problems/intersection-of-two-linked-lists

Time Complexity: O(m+ n + m) or O(2m + n)

Storage: O(1) constant

Here m is the size of the long list and n is the size of a shortlist.