题解：两个链表的第一个公共结点

写在前面

剑指offer：两个链表的第一个公共结点

知识点

• 链表处理

要求

输入两个链表，找出它们的第一个公共结点。

解法

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1||!pHead2) return nullptr;
        ListNode* cur1 = pHead1,*cur2 = pHead2;
        while(cur1&&cur2) {
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        while(cur1) {
            pHead1 = pHead1->next;
            cur1 = cur1->next;
        }
        while(cur2) {
            pHead2 = pHead2->next;
            cur2 = cur2->next;
        }
        while(pHead2&&pHead1) {
            if(pHead2==pHead1)
                return pHead1;
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        return nullptr;
    }
};

分析

设置两个指针分别cur1,cur2，首先同时遍历两个链表当其中一个走到头的时候两个指针同时停下来。这个时候两个指针之间的距离就是两个链表长度差d。再次从头开始遍历两个链表，但是此时刚才没有走到头的链表要先行d步，此时两者再同时向前走，再判断每一步的结点是否相同。

总结

链表的处理涉及多步的指针操作，需要注意边界和空指针。利用头尾相连等等的思路可以解决很多链表问题。