# #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
```javascript
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
```javascript
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
```javascript
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 月
```javascript=
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 東
```javascript=
// 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
```javascript=
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
```javascript=
/*
* 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
```javascript=
//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
```javascript=
```
:::
<br>
:::spoiler SOL
```javascript=
```
:::
---
## 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
```
Sign in with Wallet
Connect another wallet