---
# System prepended metadata

title: \#160 Intersection of Two Linked Lists
tags: [leetcode, leetcode-easy]

---

# \#160 Intersection of Two Linked Lists
## *求兩條linked list的交會點*
## Log
 - build 20210406 by syhuang

## 改良
 - 長短指針法, 以相同步數兩條list同時往前, 一頭到底之後就換到另一頭再開始, 如此最終會在相連處交會, return該節點即可, 空間複雜度降為O(1)
```javascript=
var getIntersectionNode = function(headA, headB) {
    if(!headA || !headB) return null;
    var pA = headA;
    var pB = headB;
    while(pA !== pB){
        pA = (pA==null)?headB:pA.next;
        pB = (pB==null)?headA:pB.next;
    }
    return pA;
};
```
## 初見
 - map解法, 但空間複雜度較高
```javascript=
var nodePos = new Map();
var getIntersectionNode = function(headA, headB) {
    var pa = headA;
    var pb = headB;
    while(pa){
        nodePos.set(pa,true);
        pa = pa.next;
    }
    while(pb){
        if(nodePos.has(pb)) return pb;
        pb = pb.next;
    }
    return null;
};
```
## 備註
 - javascript物件存node無法正常判斷node是否相同
## 參考
###### tags: `leetcode`, `leetcode-easy`