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

1、解题思路

1. 双指针法：使用两个指针 p1 和 p2，分别从链表 headA 和 headB 的头节点开始遍历。当 p1 到达链表 headA 的末尾时，将其重新指向 headB 的头节点；同理，当 p2 到达链表 headB 的末尾时，将其重新指向 headA 的头节点。如果两个链表有公共节点，p1 和 p2 会在公共节点处相遇；如果没有公共节点，p1 和 p2 会同时到达各自链表的末尾（即 null）。
2. 数学证明：设链表 headA 的非公共部分长度为 a，链表 headB 的非公共部分长度为 b，公共部分长度为 c。指针 p1 走过的路径为 a + c + b，指针 p2 走过的路径为 b + c + a，两者路径长度相同，因此会在公共节点处相遇。

2、代码实现

C++

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* cur1 = pHead1, *cur2 = pHead2;

        // 双指针遍历链表
        while (cur1 != cur2) {
            // 如果 cur1 到达末尾，则指向 headB 的头节点
            cur1 = cur1 ? cur1->next : pHead2;
            // 如果 p2 到达末尾，则指向 headA 的头节点
            cur2 = cur2 ? cur2->next : pHead1;
        }

        // 返回相遇的节点 (公共节点或 nullptr)
        return cur1;
    }
};

Java

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1 = pHead1, p2 = pHead2;

        // 双指针遍历链表
        while (p1 != p2) {
            // 如果 p1 到达末尾，则指向 headB 的头节点
            p1 = p1 == null ? pHead2 : p1.next;
            // 如果 p2 到达末尾，则指向 headA 的头节点
            p2 = p2 == null ? pHead1 : p2.next;
        }

        // 返回相遇的节点（公共节点或 null）
        return p1;
    }
}

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
#
# @param pHead1 ListNode类
# @param pHead2 ListNode类
# @return ListNode类
#
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        p1, p2 = pHead1, pHead2

        # 双指针遍历链表
        while p1 != p2:
            # 如果 p1 到达末尾，则指向 headB 的头节点
            p1 = p1.next if p1 else pHead2
            # 如果 p2 到达末尾，则指向 headA 的头节点
            p2 = p2.next if p2 else pHead1

        # 返回相遇的节点（公共节点或 None）
        return p1

3、复杂度分析

• 时间复杂度：O(n)，最多遍历两个链表各一次。
• 空间复杂度：O(1)，仅使用两个指针。