小学生都能看懂的题解 | #两个链表的第一个公共结点#

问题描述

假设有两条队伍，这两条队伍可能会汇合在一起。我们的任务是找到这两条队伍第一次汇合的地方。如果没有汇合的地方，我们就说这两条队伍没有交集。

解决思路

我们可以用两个小朋友来帮我们完成这个任务：

1. 两个小朋友分别站在两条队伍的最前面。
2. 一个小朋友先走一段距离，这段距离等于两条队伍汇合前的距离差。
3. 两个小朋友同时开始往前走，直到他们遇到对方。

如果两条队伍没有汇合的地方，那么这两个小朋友最终都会走到队伍的末尾，也就是说他们会在队伍的末尾相遇。

实现步骤

1. 准备两个小朋友：
1. 一个小朋友叫“小明”，他站在第一条队伍的最前面。
2. 另一个小朋友试“小红”，她站在第二条队伍的最前面。
2. 同时开始走：
1. 小明和小红同时开始走。
2. 如果小明走到队伍的末尾，他就去第二条队伍的最前面继续走。
3. 如果小红走到队伍的末尾，她就去第一条队伍的最前面继续走。
3. 找到汇合点：
1. 当小明和小红相遇时，他们相遇的地方就是队伍汇合的第一地点。
2. 如果小明和小红同时走到队伍的末尾（即都为 null），说明两条队伍没有汇合的地方。

示例代码

以下是具体的Java代码实现：

public class Solution {
    /**
     * 获取两个链表的第一个公共结点。
     * @param pHead1 第一个链表的头节点
     * @param pHead2 第二个链表的头节点
     * @return 第一个公共结点，如果没有公共结点，则返回null
     */
    public ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        // Step 1: 小明站在第一条队伍的最前面
        ListNode xiaoming = pHead1;
        // 小红站在第二条队伍的最前面
        ListNode xiaohong = pHead2;

        // Step 2: 小明和小红同时开始走
        while (xiaoming != xiaohong) {
            // 如果小明走到队伍的末尾，他就去第二条队伍的最前面继续走
            xiaoming = xiaoming == null ? pHead2 : xiaoming.next;
            // 如果小红走到队伍的末尾，她就去第一条队伍的最前面继续走
            xiaohong = xiaohong == null ? pHead1 : xiaohong.next;
        }

        // Step 3: 小明和小红相遇的地方就是汇合的第一地点
        return xiaoming;
    }
    
}

示例解释

假设输入为 {1, 2, 3}, {4, 5}, {6, 7}：

1. 初始化指针：
1. 让“小明”指向节点 1，“小红”指向节点 4。
2. 同时移动指针：
1. 当“小明”到达节点 3 的末尾时，将其移到节点 4 开始。
2. 当“小红”到达节点 5 的末尾时，将其移到节点 1 开始。
3. 找到公共节点：
1. 继续移动，最终两个指针都会到达公共节点 6。

最终输出结果为 找到的公共节点值为：6, 接下来的节点值为：7。

附件说明

有同学可能有会有疑问，为什么相遇的点就是队伍交汇的点，这里需要加减法的知识。

• a+c为队伍1的长度。
• b+c为队伍2的长度。
• (a+c)+(b+c)=(b+c)+(a+c)
• (a+c)+b=(b+c)+a
• 上面的等式的意思是，队伍1的长度+b=队伍2的长度+a

如果这篇文章对你有帮助，请点个免费的👍，让它帮助更多的人。