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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if (pHead1 == nullptr || pHead2 == nullptr) {
            return nullptr;
        }
        ListNode* p1 = pHead1;
        ListNode* p2 = pHead2;
        while (p1 != p2) {
            p1 = (p1 == nullptr) ? pHead2 : p1->next;
            p2 = (p2 == nullptr) ? pHead1 : p2->next;
        }
        return p1;
    }
};

为了解决这个问题，我们需要找到两个无环单链表的第一个公共节点。如果存在公共节点，则返回该节点；否则返回空。我们将使用双指针技巧来高效地解决这个问题，确保时间复杂度和空间复杂度满足要求。

方法思路
问题分析：两个无环单链表如果有公共节点，那么从第一个公共节点开始，后续的所有节点都是共享的。我们的任务是找到这个第一个公共节点。

关键观察：使用两个指针分别遍历两个链表。当一个指针到达链表末尾时，将其重定向到另一个链表的头部。这样，两个指针会在第一个公共节点相遇，因为它们遍历的总长度相同（两个链表的长度和）。

算法选择：使用双指针法，无需计算链表长度，通过遍历两次链表（每个指针各遍历两个链表一次）来找到公共节点。

代码解释:
初始化指针：使用两个指针 p1 和 p2 分别指向两个链表的头节点 pHead1 和 pHead2。

遍历链表：当 p1 和 p2 不相等时，继续遍历。如果 p1 到达链表末尾，则将其重定向到 pHead2；同样，如果 p2 到达链表末尾，则将其重定向到 pHead1。

相遇点：当 p1 和 p2 相遇时，该节点即为第一个公共节点。如果没有公共节点，两者会同时到达 nullptr，循环结束并返回 nullptr。

这种方法确保了在 O(n) 时间复杂度和 O(1) 空间复杂度内解决问题，高效且简洁。