Easy: Find the merge point between two lists.
Published: 2020-11-13 11:12:44

```
Explanation:
List1  
15
 \     List2
  4    6
   \  /
    3
    |
    2
For List1 & List2, the merge-point is 3, Where these two lists referentially target 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.

```
interface ListNode {
  val: number;
  next: ListNode | null;
}

function countNodes(list: ListNode | null) {
  let count = 0;
  let ptr = list;
  while (ptr != null) {
    count++;
    ptr = ptr.next;
  }
  return count;
}

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  const countA = countNodes(headA);
  const countB = countNodes(headB);
  let diff = Math.abs(countA - countB);
  let [long, short] = countA - countB < 0 ? [headB, headA] : [headA, headB];
  let ptr = long;

  while (diff > 0) {
    ptr = ptr && ptr.next;
    diff--;
  }

  while (ptr != null && short != null) {
    if (ptr == short) return ptr;
    ptr = ptr.next;
    short = short.next;
  }
  return null;
};
```

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.