算法的学习笔记—两个链表的第一个公共结点(牛客JZ52)

😀前言
在链表问题中，寻找两个链表的第一个公共结点是一个经典问题。这个问题的本质是在两个单链表中找到它们的相交点，或者说它们开始共享相同节点的地方。本文将详细讲解这个问题的解题思路，并提供一种高效的解决方法。

🏠个人主页：尘觉主页

🥰两个链表的第一个公共结点

NowCoder

😄题目描述

😊问题描述

给定两个单向链表，找出它们的第一个公共节点。如果两个链表没有交点，则返回 null。这意味着链表从某个结点之后开始共享相同的后续节点。需要注意的是，这里的"公共"结点不是指值相同，而是指两个链表引用的同一个结点，即在内存中的地址相同。

🥳解题思路

解决这个问题的核心在于如何找到链表的第一个公共节点。可以通过观察链表的结构来思考：

设链表 A 的长度为 a + c，其中 a 是链表 A 不与链表 B 共享的部分的长度，c 是 A 和 B 共有的部分长度。同样地，设链表 B 的长度为 b + c，其中 b 是链表 B 不与链表 A 共享的部分。两条链表在某个节点开始共享尾部节点，因此可以得到以下等式：

• 链表 A 的总长度 = a + c
• 链表 B 的总长度 = b + c

可知：

• 如果我们从头开始遍历链表 A 和链表 B，由于它们的长度不同，直接同时遍历无法保证两条链表的指针在公共部分的第一个节点相遇。
• 但是，如果我们遍历完一条链表后，切换到另一条链表继续遍历，则可以通过控制遍历的顺序来同步两个指针的速度。即遍历完链表 A 后从链表 B 的头部重新开始遍历，同样地，遍历完链表 B 后从链表 A 的头部重新开始遍历。

通过这样的方式，两个指针会在相同的时刻访问到链表的公共部分。具体步骤如下：

1. 初始化两个指针 l1 和 l2，分别指向链表 A 和链表 B 的头节点。
2. 如果 l1 和 l2 不相等，则分别遍历链表 A 和 B。当某个指针到达尾部时，切换到另一条链表的头部继续遍历。
3. 当两个指针相遇时，返回该指针所指向的节点，即第一个公共节点。

时间复杂度和空间复杂度分析

• 时间复杂度： O(m + n)，其中 m 和 n 分别是链表 A 和 B 的长度。每个指针遍历链表的次数最多为两次，因此时间复杂度为 O(m + n)。
• 空间复杂度： O(1)，只用了两个指针来进行遍历，因此不需要额外的空间。

💝代码实现

下面是基于上述思路的 Java 实现代码：

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 l1 = pHead1;ListNode l2 = pHead2;// 当两个指针不相等时，继续遍历while (l1 != l2) {// l1 先走完链表 A，转向链表 Bl1 = (l1 == null) ? pHead2 : l1.next;// l2 先走完链表 B，转向链表 Al2 = (l2 == null) ? pHead1 : l2.next;}// 相遇时即为第一个公共结点，或者为 null（无公共节点）return l1;}
}

代码详解

1. ListNode 类：定义了链表的节点结构，每个节点包含一个整数值 val 和指向下一个节点的指针 next。
2. FindFirstCommonNode 方法：该方法接受两个链表的头节点作为参数，并返回第一个公共节点。遍历链表的方式如前面所述，通过指针的切换，两个指针会在公共节点相遇。

示例

考虑以下两个链表：

链表 A: 1 -> 2 -> 3 -> 6 -> 7
链表 B: 4 -> 5 -> 6 -> 7

在这种情况下，链表 A 和 B 的第一个公共节点是 6。通过上述方法，程序会正确找到该节点。

😄总结

通过同步两个指针的遍历方式，能够有效地解决两个链表寻找第一个公共节点的问题。该方法的时间复杂度为 O(m + n)，空间复杂度为 O(1)，在链表问题中是非常高效的一种解法。这种技巧值得学习，因为它不仅解决了本题，还可以运用于其他链表相关的题目中，比如寻找链表的环起点等。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞