【160】相交链表

方法一：双指针法

算法思想：
使用两个指针p1，p2分别遍历headA和headB。
当p1遍历完headA或p2遍历完headB，我们让该指针去遍历另一个链表。
由于两个指针走的路程相同，所以若两链表相交，则p1，p2一定会在第一个交点处相遇。
若两个链表不相交则p1，p2会同时指向空。
代码：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p1 = headA, *p2 = headB;
        while (p1 != p2){
            if (p1 == nullptr) p1 = headB;
            else p1 = p1->next;
            if (p2 == nullptr) p2 = headA;
            else p2 = p2->next;
        }
        return p1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

方法二：对齐法

算法思路：
先找到较长的链表，并计算两个链表的长度之差dist，使长链表先进行遍历，走完这个长度之差dist，使得两个链表对齐。
而后，令短链表和长链表同步开始遍历。
若两链表相交，则p1，p2一定会在第一个交点处相遇。
若两个链表不相交则p1，p2会同时指向空。
代码：

class Solution {
public:

    int getLen(ListNode* head){
        ListNode* p = head;
        int len = 0;
        while (p != nullptr){
            len ++;
            p = p->next;
        }
        return len;
    }

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* longList = headA, *shortList = headB;
        int len1 = getLen(longList), len2 = getLen(shortList);
        int dist = len1 - len2;
        if (dist < 0){
            longList = headB;
            shortList = headA;
            dist = len2 - len1;
        }
        
        while (dist --){
            longList = longList->next;
        }

        while (longList != shortList){
            longList = longList->next;
            shortList = shortList->next;
        }
        return longList;
    }
};
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