#3 160. Intersection of Two Linked Lists

tags:linked list easy leetcode

Problem

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

Note that the linked lists must retain their original structure after the function returns


Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

• intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
• listA - The first linked list.
• listB - The second linked list.
• skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
• skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

• testcase:
  ​​​​8
  ​​​​[4,1,8,4,5]
  ​​​​[5,6,1,8,4,5]
  ​​​​2
  ​​​​3
  

Sample Input & Output

Example 1

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.

Explanation: The two lists do not intersect, so return null.

Constraints

• intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Follow up

Could you write a solution that runs in O(m + n) time and use only O(1) memory?

Solutions

Official

none.

---

Everyone's

solution 1: record the nodes

月

var getIntersectionNode = function(headA, headB) {
    // Time O(a+b) Space O(a)
    // a is the length of headA; b is the length of headB
    
    const recordSet = new Set();
    // set headA node in recordSet
    while(headA) {
        recordSet.add(headA);
        headA = headA.next;
    }
    while(headB) {
        if (recordSet.has(headB)) {
            return headB;
        }
        headB = headB.next;
    }
    return null;
};

solution 2: truncate the list

東

// Time O(m+n), Space O(m+n) m, n is the amount of node of input headA, headB
var getIntersectionNode = function(headA, headB) {
    let listA = headA;
    let listB = headB;
    const lenA = calculateLength(headA);
    const lenB = calculateLength(headB);
    
    if(lenA > lenB){
        const AStartIdx = lenA - lenB;
        listA = moveListToIdx(listA, AStartIdx);
    } else{
        const BStartIdx = lenB - lenA;
        listB = moveListToIdx(listB, BStartIdx);
    }
    
    while(listA !== null){
        if(listA === listB){
            return listA;
        }
        listA = listA.next;
        listB = listB.next;
    }
    return null;
};

function calculateLength(list){
    let count = 0;
    while(list !== null){
        count ++;
        list = list.next;
    }
    return count;
}
    
function moveListToIdx(list, idx){
    while(idx > 0){
        list = list.next;
        idx --;
    }
    return list;
}

solution 3: loop the list

Raiy

var getIntersectionNode = function(headA, headB) {
    // time: O(n+m)? space: O(1) n = headA length, m = headB length 
    // -> time: O(n*m) : the worst case
   if(!headA || !headB) return null
    
   let currentA = headA
   let currentB = headB
   
   while(currentA !== currentB){
       currentA = currentA.next
       currentB = currentB.next
       
       if(currentA === currentB){
           return currentA
       }
     
       if(!currentA) currentA = headA
       if(!currentB) currentB = headB
   }

    
    return currentA
};

solution 4: concatenate two lists

YC

/*
 * time: O(m+n), where m is the number of nodes in the headA, n is the number of nodes in the headB 
 * space: O(1)
 */
var getIntersectionNode = function(headA, headB) {
    let listA = headA;
    let listB = headB;
    while(listA !== listB){
        listA = listA === null ? headB : listA.next;
        listB = listB === null ? headA : listB.next;
    }
    return listA;
};

Becky

//time: O(n) | space: O(1)
//-> time: O(m+n)
var getIntersectionNode = function(headA, headB) {
    let a = headA;
    let b = headB;
    
    while (a != b) {
        if(a === null){
            a = headB;
        }else{
            a = a.next;
        }

        if(b === null){
            b = headA;
        }else{
            b = b.next
        }
    }
    
    return a;
};

backlog

Hao

SOL

---

Supplement / Discussion

(示意圖)

Thinking 1

直觀的做法：把 A 的 node 存起來，遍歷 B 找重複的點

Thinking 2

直觀的做法：既然 B 比 A 長，那就讓 B 從 b2 開始判斷。

計算 A, B 的總長，取差值 B - A，loop 找出 c1

A:     a1  c1  c2
 
B: b1  b2  c1  c2

⬇️

A:     a1  c1  c2
 
B:     b2  c1  c2

Thinking 3

如果 A 和 B 同時從頭開始尋找相交的點，會在什麼時候找到 c1

list 不斷重複自己

A: a1  c1  c2| a1  c1  c2| a1  c1  c2| a1  c1  c2
 
B: b1  b2  c1  c2| b1  b2  c1  c2| b1  b2  c1  c2 

在 A 重複自己四次、B 重複自己三次後，找到 c1 了

有發現什麼有趣的現象嗎？

Thinking 4

從 Thinking 3 可以發現，出現相交的點後，A 和 B 最後的長度會一樣長。

還有其他方法可以讓兩者的長度一樣嗎？

A + B = B + A

回頭看看 Follow up

Could you write a solution that runs in O(m + n) time and use only O(1) memory?

A: a1  c1  c2
 
B: b1  b2  c1  c2

⬇️

A + B: a1  c1  c2| b1  b2  c1  c2

B + A: b1  b2  c1  c2| a1  c1  c2