剑指offer-36、两个链表的第⼀个公共节点
<h2 id="题描述">题⽬描述</h2><p>输⼊两个链表，找出它们的第⼀个公共结点。（注意因为传⼊数据是链表，所以错误测试数据的提示是⽤其他⽅式显示的，保证传⼊数据是正确的）</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="hashset包含法">HashSet包含法</h3>
<p>第⼀种做法，直接依赖于 HashSet ，遍历第⼀个链表的时候，将所有的节点，添加到 hashset 中，</p>
<p>遍历第⼆个链表的时候直接判断是否包含即可，属于空间换时间的做法。</p>
<pre><code class="language-java">public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) return null;
// 使用HashSet存储第一个链表的所有节点
HashSet<ListNode> visited = new HashSet<>();
// 遍历第一个链表，将所有节点加入集合
ListNode current = pHead1;
while (current != null) {
visited.add(current);
current = current.next;
}
// 遍历第二个链表，检查节点是否在集合中
current = pHead2;
while (current != null) {
if (visited.contains(current)) {
return current; // 找到第一个公共节点
}
current = current.next;
}
return null; // 没有公共节点
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(m+n)，需要遍历两个链表各一次</li>
<li><strong>空间复杂度</strong>：O(min(m,n))，存储较短链表的节点</li>
</ul>
<h3 id="双栈法">双栈法</h3>
<p>利用栈的后进先出特性，从链表尾部开始比较，找到最后一个相同的节点。公共节点之后的节点都是相同的，所以从后往前比较，最后一个相同的节点就是第一个公共节点</p>
<pre><code class="language-java">import java.util.Stack;
public class Solution {
/**
* 使用双栈查找两个链表的第一个公共节点
* 思路：将两个链表分别压入栈中，然后同时出栈比较
* 时间复杂度：O(m+n)，空间复杂度：O(m+n)
*/
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) return null;
Stack<ListNode> stack1 = new Stack<>();
Stack<ListNode> stack2 = new Stack<>();
// 将两个链表的所有节点分别压入栈中
ListNode current = pHead1;
while (current != null) {
stack1.push(current);
current = current.next;
}
current = pHead2;
while (current != null) {
stack2.push(current);
current = current.next;
}
ListNode commonNode = null;
// 同时从两个栈弹出节点进行比较
while (!stack1.isEmpty() && !stack2.isEmpty()) {
ListNode node1 = stack1.pop();
ListNode node2 = stack2.pop();
if (node1 == node2) {
commonNode = node1; // 记录公共节点
} else {
break; // 遇到不同节点，停止比较
}
}
return commonNode;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(m+n)，需要遍历两个链表各两次（压栈和出栈）</li>
<li><strong>空间复杂度</strong>：O(m+n)，需要两个栈存储所有节点</li>
</ul>
<h3 id="长度差法推荐">长度差法（推荐）</h3>
<p>可以将两个链表想象为两段路程，公共节点是终点。让长的链表先走多出的距离，然后同时前进，就能同时到达公共节点</p>
<p>譬如现在有⼀个链表 1->2->3->6->7 ，另外⼀个链表 4->5->6->7 ，明显可以看出第⼀个公共节点是6 。</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201654858.png" alt="" loading="lazy"></p>
<p>最直接的⽅法，每⼀个链表都遍历⼀次，计算链表中的个数，⽐如 1->2->3->6->7 个数为5， 4->5->6->7 个数为4，两者相差1（设为k）个。</p>
<p>我们可以使⽤两个指针，分别指向链表的头部。然后让第⼀个链表的指针先⾛ k=1 步。</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201654627.png" alt="" loading="lazy"></p>
<p>这样就相当于指针后⾯的两个链表等⻓了。</p>
<p>就可以开始⽐较，如果不相等，则两个指针都往后移动即可，知道节点为null。</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201654832.png" alt="" loading="lazy"></p>
<pre><code class="language-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) {
// 只要有⼀个为空，就不存在共同节点
if (pHead1 == null || pHead2 == null) {
return null;
}
// 计算链表1中的节点个数
int numOfListNode1 = 0;
ListNode head1 = pHead1;
while (head1 != null) {
numOfListNode1++;
head1 = head1.next;
}
// 计算链表2中节点个数
int numOfListNode2 = 0;
ListNode head2 = pHead2;
while (head2 != null) {
numOfListNode2++;
head2 = head2.next;
}
// ⽐较两个链表的⻓度
int step = numOfListNode1 - numOfListNode2;
if (step > 0) {
// 链表1更⻓，链表1移动
while (step != 0) {
pHead1 = pHead1.next;
step--;
}
} else {
// 链表2更⻓，链表2移动
while (step != 0) {
pHead2 = pHead2.next;
step++;
}
}
// 循环遍历后⾯的节点，相等则返回
while (pHead1 != null && pHead2 != null) {
if (pHead1 == pHead2) {
return pHead1;
} else {
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
}
return null;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(m+n)，需要遍历链表三次（两次计算长度，一次查找）</li>
<li><strong>空间复杂度</strong>：O(1)，只使用常数级别额外空间</li>
</ul>
<p>但是上⾯的做法，如果公共节点在最后⼀个，假设⼀个链表⻓度为 n ，⼀个为 m ，那么计算个数就要全部遍历，需要 n+m 。两个链表都移动，到最后⼀个节点的时候才相等，也是 n+m ，也就是 O(2*(n+m)) 。</p>
<h3 id="双指针遍历法最优">双指针遍历法（最优）</h3>
<p>有没有更加好⽤的做法呢？肯定有，我们来看：</p>
<p>两个链表分别是：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201657668.png" alt="" loading="lazy"></p>
<p>如果我在第⼀个链表后⾯拼接上第⼆个链表，第⼆个链表后⾯拼接上第⼀个链表，就会变成下⾯的样⼦：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201657883.png" alt="" loading="lazy"></p>
<p>发现了⼀个规律，也就是拼接之后的链表，是等⻓度的，第⼀个和第⼆个链表都从第⼀个开始⽐较，只要相等，就说明是第⼀个公共节点。也就是上⾯被圈起来的 6 节点。</p>
<p>原理如下：</p>
<ul>
<li>设链表1独有部分长度为a，链表2独有部分长度为b，公共部分长度为c</li>
<li>指针p1路径：a + c + b</li>
<li>指针p2路径：b + c + a</li>
<li>两个指针路径长度相同，会在公共节点相遇</li>
</ul>
<p><strong>特殊情况处理：</strong>当两个链表没有公共节点时，两个指针会同时变为null，退出循环</p>
<pre><code class="language-java">public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
// 只要有⼀个为空，就不存在共同节点
if (pHead1 == null || pHead2 == null) {
return null;
}
ListNode head1 = pHead1;
ListNode head2 = pHead2;
while (head1 !=head2) {
// 如果下⼀个节点为空，则切换到另⼀个链表的头节点，否则下⼀个节点
head1 = (head1 == null) ? pHead2 : head1.next;
head2 = (head2 == null) ? pHead1 : head2.next;
}
return head1;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(m+n)，每个指针遍历两个链表各一次</li>
<li><strong>空间复杂度</strong>：O(1)，只使用两个指针</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19203921
頁:
[1]