160. 相交链表
#链表 2024-09-23 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        // 求两个链表长度的差 len
        ListNode* Aindex = headA;
        int ALen = 0;
        while (Aindex) {
            ALen++;
            Aindex = Aindex->next;
        }
        ListNode* Bindex = headB;
        int BLen = 0;
        while (Bindex) {
            BLen++;
            Bindex = Bindex->next;
        }

        // 让最长的链表 移动 len
        int len = abs(ALen - BLen);
        Aindex = headA;
        Bindex = headB;
        if(ALen < BLen){
            swap(Aindex,Bindex);
        }

        for(int i = 0; i < len; i++){
            Aindex = Aindex->next;
        }

        // 齐头并进，地址相等即为第一次交汇点
        while(Aindex){
            if(Aindex == Bindex){
                return Aindex;
            }
            Aindex = Aindex->next;
            Bindex = Bindex->next;
        }

        return NULL;
    }
};

交互点指的是比较两个节点的地址是否相等，而不是元素相等，务必弄清楚。

解此题的步骤：

  1. 求两个链表长度的差 len
  2. 让最长的链表 移动 len
  3. 齐头并进，地址相等即为第一次交汇点