# 160. Intersection of Two Linked Lists

{% embed url="<https://leetcode.com/problems/intersection-of-two-linked-lists/>" %}

### Stack

1. 两个链表找交叉点，基本思路肯定是一直**同步迭代指针**直到出现临界情况。
2. 指针正向迭代的临界情况是`开始指向同一个 node` ，但因为链表长度可能不同，两个指针直接同步移动会错开，打不到同一个node上。
3. 没办法正向就反向，临界变成了`开始指向不同 node`，而在临界前只需要同步移动指针（一直指的相同node）即可。
4. 怎么实现反向迭代呢？给`ListNode`对象加属性太麻烦了，直接`stack`记录链接关系，然后一直`pop`即可实现反向。

### 砍头统一

1. 正向迭代移动指针的问题是，两个链表交叉的位置可能跟两个`head`的距离不一样，导致没办法同步移动。
2. 那就想办法让这两个距离一样。
3. 直接先跑完两个链表，分别记录长度，计算长度差`diff`，然后把长的那个砍掉头上的`diff`，实现两个链表长度一致的情况。
4. 然后开始同步移动指针，指针指向位置相同即为intersection的开始。

这道题拿 Python 写的时候很适合复习知识点：

`==`和`is`在python有什么不同？前者是变量内容是否相等，后者是变量是否指向内存中同一个地址。虽然这题`==`在这个方法里也可以，但`is` 还是严谨一些。

{% tabs %}
{% tab title="Stack (C++)" %}

```cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        stack<ListNode*> A, B;
        ListNode *curA = headA, *curB = headB;
        while(curA) {
            A.push(curA);
            curA = curA->next;
        }
        while(curB) {
            B.push(curB);
            curB = curB->next;
        }
        ListNode *prev = NULL;
        while(!A.empty() && !B.empty() && (A.top()==B.top())) {
            prev = A.top();
            A.pop();
            B.pop();
        }
        return prev; // 函数指定返回的是指针
        
    }
};
```

{% endtab %}

{% tab title="砍头统一 python" %}

```python
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        lenA, lenB = 0, 0
        curA, curB = headA, headB
        while curA:
            lenA+=1
            curA = curA.next
        while curB:
            lenB+=1
            curB = curB.next
        # 确保A是比较长的那个，因为一会儿要砍A的头
        if lenA < lenB:
            headA, headB = headB, headA
        diff = abs(lenA-lenB)
        # 给A砍头
        for _ in range(diff):
            headA = headA.next 
        while headA and headB and headA is not headB:
            headA = headA.next
            headB = headB.next
        return headA
```

{% endtab %}
{% endtabs %}

比较讨巧的解法是借鉴Q202用过的龟兔赛跑。

{% content-ref url="202.-happy-number" %}
[202.-happy-number](https://xuqiangwen1994.gitbook.io/practice/202.-happy-number)
{% endcontent-ref %}
