AcWing 66. 图解双指针法

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 66. 图解双指针法原题链接简单

作者：

Hasity , 2020-12-08 20:07:13 , 所有人可见 , 阅读 5241

146

94

题解
1. 用两个指针 p1，p2 分别指向两个链表 headA，headB 的头结点，同时向后遍历。
2. 当指针到达链表末尾时，重新定位到另一个链表的头结点。
3. 当它们相遇时，所指向的结点就是第一个公共结点。

解释
设A链表的非公共部分长度为LA，B链表的非公共部分长度为LB，公共部分长度为C。

360截图20201206224658719.jpg

A链表总长度为LA + C，B链表总长度为LB + C。
当指针按照题解方式走下去，p1第二次走到公共节点的时候，走过的长度为LA + C + LB，p2第二次走到公共节点的时候，走过的长度为LB + C + LA。p1 p2走过的长度相等，p1 p2 相遇。
所以，当p1 p2 相遇（相等）的时候，指向的节点就是公共节点。

//cpp
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *p1 = headA;
        ListNode *p2 = headB;

        while (p1 != p2) {
            if(p1 != NULL)//p1没有走到结尾
                p1 = p1->next;//p1指向下一个节点
            else//p1走到结尾
                p1 = headB;//p1指向另一个链表头
            if(p2 != NULL)//p2没有走到结尾
                p2 = p2->next;//p2指向下一个节点
            else  //p2走到结尾 
                p2 = headA;//p2指向另一个链表头
        }
        return p1;
    }
};