160. Intersection of Two Linked Lists

Loading...LeetCode

Stack

1. 两个链表找交叉点，基本思路肯定是一直同步迭代指针直到出现临界情况。

2. 指针正向迭代的临界情况是开始指向同一个 node ，但因为链表长度可能不同，两个指针直接同步移动会错开，打不到同一个node上。

3. 没办法正向就反向，临界变成了开始指向不同 node，而在临界前只需要同步移动指针（一直指的相同node）即可。

4. 怎么实现反向迭代呢？给ListNode对象加属性太麻烦了，直接stack记录链接关系，然后一直pop即可实现反向。

砍头统一

1. 正向迭代移动指针的问题是，两个链表交叉的位置可能跟两个head的距离不一样，导致没办法同步移动。

2. 那就想办法让这两个距离一样。

3. 直接先跑完两个链表，分别记录长度，计算长度差diff，然后把长的那个砍掉头上的diff，实现两个链表长度一致的情况。

4. 然后开始同步移动指针，指针指向位置相同即为intersection的开始。

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

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

Stack (C++)

/**
 * 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; // 函数指定返回的是指针
        
    }
};

砍头统一 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

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

202. Happy Number