[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 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; } 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 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; } // 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]