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

这道题我自己想到一种解法，评论区看到一位大神的写法，两种方法都放在了代码片里。

我自己想到的方法就是人为构造环，继续采用题目BM7 的做法，然后把环破开
而BM7的做法，我写过题解，链接是：题解 | #链表中环的入口结点#

图片如下：

至于大神的做法，我就不多做评论了，实在太强！

• 当pHead1和pHead2指向的链表的长度相同时，如果
  • 两个链表没有公共点，则p1和p2在访问到尾结点之后，都会等于 NULL
  • 两个链表有公共点，则p1和p2第一次相遇的位置就是这个公共点
• 当pHead1和pHead2指向的链表的长度不同时，如果
  • 第一个链表的独有部分的长度（记为a）< 第二个链表的独有部分的长度（记为b），p1会比p2先到达链表公共部分的末端，也就是NULL,之后p1会指向第二个链表，继续遍历b个节点后到达公共点；而与此同时，p2在到达NULL之后也会继续从第一个链表的开头进行遍历，遍历a个节点之后就可以与p1相逢。相逢的时候，p1和p2走过的长度都是（a+b+common）

代码如下：

#define PUTN(pnode) (printf(">> " #pnode ": %d\n", pnode->val))
class Solution {
public:
    ListNode* FindFirstCommonNode1( ListNode* pHead1, ListNode* pHead2) {
        // 这道题目，可以仿照求环的入口节点那样使用快慢指针来做
        // 什么？不是没有环吗？
        // 没有环，那就创造环
        // 从 pHead1 出发，可以到达第一个链表的尾结点
        // 之后把 tail->next = phead1
        // 然后从 pHead2 开始使用双指针
        // 最后把 tail->next 还原
        if (pHead1 == pHead2) return pHead1;
        if (!pHead1 or !pHead2) return nullptr;

        ListNode *tail = pHead1;
        while (tail->next) {
            tail = tail->next;
        } // tail 最终指向尾结点
        tail->next = pHead1;

        ListNode *fast = pHead2;
        ListNode *slow = pHead2;

        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                break;
            }
        }
        if (fast != slow) return nullptr;

        // 现在 fast 和 slow 相遇在 node_m
        // 要寻找node_x, 需要 fast 移动到 pHead2, 之后每次一步
        fast = pHead2;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        tail->next = nullptr;
        return fast;
    }

    ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
        ListNode *p1 = pHead1;
        ListNode *p2 = pHead2;
        while(p1!=p2){
            p1 = (p1==NULL ? pHead2 : p1->next);
            p2 = (p2==NULL ? pHead1 : p2->next);
        }
        return p1;
    }
};