[tabby title=”Task”]

**Write a program to find the node at which the intersection of two singly linked lists begins.**

For example, the following two linked lists:

begin to intersect at node c1.

**Example 1:**

This problem was taken from Leetcode

[tabby title=”Solution”]

** We are not asked to compare the values inside the linked lists but the list node objects, so we could ignore the values of the list.**

#### Approach 1: Brute Force

For each node a_{i} in list A, traverse the entire list B and check if any node in list B coincides with a_{i}.

**Complexity Analysis**

- Time complexity : $O(mn)$.
- Space complexity : $O(1)$.

#### Approach 2: Calculating the length of the two linked lists and compare the elements that could potentially intersect.

- Time complexity : $O(m+n)$.
- Space complexity : $O(m)$ or $O(n)$.

function ListNode(val) { this.val = val; this.next = null; } headA = new ListNode(4); headA.next = new ListNode(1); headB = new ListNode(5); headB.next = new ListNode(0); headB.next.next = new ListNode(1); headA.next.next = headB.next.next.next = new ListNode(8); headB.next.next.next.next = headA.next.next.next = new ListNode(4); headB.next.next.next.next.next = headA.next.next.next.next = new ListNode(5); /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { let node = headA; let countA = 0; while(node != null ) { node = node.next; countA ++; } node = headB; let countB = 0; while(node != null ) { node = node.next; countB ++; } let longList, shortList, diff, iteratorLongLength,iteratorShortLength; if(countA > countB) longList = headA, shortList = headB, diff = countA - countB; else longList = headB, shortList = headA, diff = countB - countA; let i = 0; while(shortList != null) { if(i < diff ) { longList = longList.next; } else { console.log("long list, short list", longList.val, shortList.val); if(longList == shortList) return longList.val; longList = longList.next; shortList = shortList.next; } i ++; } }; console.log (getIntersectionNode(headA, headB) );

*what we just did:*

*– we calculated the length of the first list to be 5 and the second 6 (first and the second loop)*

*– the third loop is doing two things:*

*– first since the difference between the shorter and the longer list is 1 we move the cursor to the second element of the longer list (lines 59-61)*

*– after we position the longer list cursor at the second element we could start comparing (line 64)*

If we execute the function we will see this result:

`long list, short list 0 4`

long list, short list 1 1

long list, short list 8 8

And the third element is exactly where the intersection is.

#### Approach 3: Traverse both lists and when reaching the end of each one, move the pointer to the opposite list and traverse again till intersection is found.

- Time complexity : $O(m+n)$.
- Space complexity : $O(m)$ or $O(n)$.

This basically is the same concept as in the example above, just written in a bit more elegant way.

function ListNode(val) { this.val = val; this.next = null; } headA = new ListNode(4); headA.next = new ListNode(1); headB = new ListNode(5); headB.next = new ListNode(0); headB.next.next = new ListNode(1); headA.next.next = headB.next.next.next = new ListNode(8); headB.next.next.next.next = headA.next.next.next = new ListNode(4); headB.next.next.next.next.next = headA.next.next.next.next = new ListNode(5); /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { let nodeA = headA; let nodeB = headB; let swapA = false; let swapB = false; var i = 0; while(nodeA != null && nodeB!=null ) { // node A if(!swapA && nodeA.next == null) { nodeA = headB; swapA = true; } else { nodeA = nodeA.next; } // node B if(!swapB && nodeB.next == null) { nodeB = headA; swapB = true; } else { nodeB = nodeB.next; } if(nodeA === nodeB) return nodeA.val; } }; console.log (getIntersectionNode(headA, headB) );

*what we just did:*

– traverse listA and listB till we reach the end of each one (lines 47 and 55) .

– once we reach the end of each list we point the cursor to the opposite list (lines 43 and 51)

#### Approach 4: Hash Table

Traverse list A and store the address / reference to each node in a hash set. Then check every node b_{i} in list B: if b_{i} appears in the hash set, then b_{i} is the intersection node.

**Complexity Analysis**

- Time complexity : $O(m+n)$.
- Space complexity : $O(m)$ or $O(n)$.

function ListNode(val) { this.val = val; this.next = null; } // link-list A: [4,1,8,4,5] // link-list B: [5,0,1,8,4,5] headA = new ListNode(4); headA.next = new ListNode(1); headB = new ListNode(5); headB.next = new ListNode(0); headB.next.next = new ListNode(1); headA.next.next = headB.next.next.next = new ListNode(8); headB.next.next.next.next = headA.next.next.next = new ListNode(4); headB.next.next.next.next.next = headA.next.next.next.next = new ListNode(5); /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { let hashMap = {}; let node = headA; while(node != null ) { hashMap[node.val] = node; node = node.next; } node = headB; while(node != null) { let val = node.val; if(hashMap[val] == node) { return val; } node = node.next; } }; console.log ("result: ", getIntersectionNode(headA, headB) );

[tabbyending]