# Intersection of Two Linked Lists

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

## 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 ai in list A, traverse the entire list B and check if any node in list B coincides with ai.

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;
}

/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @return {ListNode}
*/

let countA = 0;
while(node != null ) {
node = node.next;
countA ++;
}

let countB = 0;
while(node != null ) {
node = node.next;
countB ++;
}

let longList, shortList, diff, iteratorLongLength,iteratorShortLength;
if(countA > countB)
else

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;
}

/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @return {ListNode}
*/

let swapA = false;
let swapB = false;
var i = 0;
while(nodeA != null && nodeB!=null ) {
// node A
if(!swapA && nodeA.next == null) {
swapA = true;
}
else {
nodeA = nodeA.next;
}
// node B
if(!swapB && nodeB.next == null) {
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 bi in list B: if bi appears in the hash set, then bi 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;
}

/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @return {ListNode}
*/

let hashMap = {};
while(node != null ) {

hashMap[node.val] = node;
node = node.next;
}

console.log ("result: ", getIntersectionNode(headA, headB) );