(复刷) 面试题02.07.链表相交

原题链接：面试题02.07.链表相交

思路：
求相交的起始结点，并不是值相交，而是结点相交，那么也就代表判断条件是指针指向的位置相等即可

A、B链表长度可能不一致，假设他们一定有相交的结点
那么需要做的 就是直接统一A和B链表的长度，然后一起从头遍历，指针指向的位置是否相同，相同则代表相交，返回相交的指针就可以
如果没有返回相交的指针，那就代表这两个链表没有相交的结点，返回NULL即可

全代码：

/**
 * 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) {
        //遍历headA链表和headB链表的长度
        ListNode* heada = headA;
        ListNode* headb = headB;
        //统计headA和headB的长度
        int lenA = 0;
        int lenB = 0;

        while(heada != NULL)
        {//统计headA长度
            heada = heada ->next;
            lenA++;
        }
        while(headb != NULL)
        {//统计headB长度
            headb = headb ->next;
            lenB++;
        }
        if(lenA < lenB)
        {//交换， 让链表A成为最长的链表
            swap(lenA,lenB);
            swap(headA,headB);
        }
        //求交点，是指针指向的位置相同 而不是值相同
        int len = lenA - lenB;
        //将指针重新指向新headA和headB
        heada = headA;
        headb = headB;

        while(len--)
        {//让lenA指针移动到和lenB一样开头的地方
            heada = heada ->next;
        }
        while(heada != NULL)
        {//开始判断相交点，如果不相交则一直更新位置
            if(heada == headb)
            {//相交返回相交的指针
                return heada;
            }
            heada = heada ->next;
            headb = headb ->next;
        }
        return NULL;
    }
};
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55