# #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`:
<br/>


<br/>
The test cases are generated such that there are no cycles anywhere in the entire linked structure.

**Note** that the linked lists must **retain their original structure** after the function returns
<br/>
**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?

<br>

## Solutions

### Official
none.
<br>

---

### Everyone's
#### solution 1: record the nodes

:::spoiler 月

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

:::

<br>

#### solution 2: truncate the list

:::spoiler 東

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

:::
<br/>

#### solution 3: loop the list
:::spoiler 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
};

:::

<br>

#### solution 4: concatenate two lists

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

:::

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

:::

<br>

<br>

#### backlog

:::spoiler Hao

:::

<br>

:::spoiler 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 了

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

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

還有其他方法可以讓兩者的長度一樣嗎？
> A + B = B + A

:::spoiler 回頭看看 Follow up
Could you write a solution that runs in `O(m + n)` time and use only `O(1)` memory?
:::
<br/>

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