66. 两个链表的第一个公共结点

66. 两个链表的第一个公共结点

 

解题思路:

定义2个指针p、q。

有公共节点的情况:

不同部分为a, 和b,公共部分为c;让两个指针一起走,p从a走到c就转向b, q从b走到c转向a,有a + c + b = b + c + a,则p和q在公共节点相遇。

 

没有公共节点:

p从a走到头就转向b;q从b走到头转向a。a+b=b+a,p和q会在空节点相遇。

66. 两个链表的第一个公共结点

 

 

 

 

class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        

        ListNode *p = headA, *q = headB;//auto p = headA, q = headB;
        while(p != q) {
            if(p) p = p->next;
            else p = headB;
            if (q) q = q->next;
            else q = headA;
        }
        return p;

    }
};

其中ListNode *p = headA, *q = headB;

可以写成  auto p = headA, q = headB;

上一篇:Intersection of Two Linked Lists


下一篇:数据结构-链表习题(部分)