剑指offer-55、链表中环的⼊⼝节点
<h2 id="题描述">题⽬描述</h2><p>给⼀个链表，若其中包含环，请找出该链表的环的⼊⼝结点，否则，输出null 。</p>
<p>例如，输⼊{1,2},{3,4,5} 时，对应的环形链表如下图所示：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231828272.png" alt="" loading="lazy"></p>
<p>可以看到环的⼊⼝结点的结点值为3，所以返回结点值为3的结点。</p>
<p>给定的链表节点的结构：</p>
<pre><code class="language-java">public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
</code></pre>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="借用hashset">借用HashSet</h3>
<p>直接使⽤ HashSet ,历链表的时候，如果 HashSet 中不包含，则添加到 HashSet 中，如果链表中包含，说明已经回到环的第⼀个节点。Java 代码实现如下：</p>
<pre><code class="language-java">public ListNode EntryNodeOfLoop(ListNode pHead) {
HashSet set = new HashSet();
while(pHead!=null){
if(set.contains(pHead)){
return pHead;
}else{
set.add(pHead);
pHead = pHead.next;
}
}
return null;
}
</code></pre>
<ul>
<li>时间复杂度：O(n) - 每个节点最多访问一次</li>
<li>空间复杂度：O(n) - 最坏情况下需要存储所有节点</li>
</ul>
<h3 id="双指针">双指针</h3>
<p>上⾯的做法时间复杂度为O(n) ，由于借助了⼀个hashSet ，空间复杂度也为O(n) 。那假设我们不需要使⽤额外的空间呢？怎么做呢？</p>
<p>使⽤快慢双指针，⼀个⼀次⾛⼀步，⼀个⼀次⾛两步，当两个重合在⼀起的时候，这时候，并不是环的⼊⼝节点。只能说明两个指针，⼀个⽐另外⼀个多⾛了若⼲圈，可能是⼀圈，可能是2 ， 3 圈。</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231830875.png" alt="" loading="lazy"></p>
<p>⽐如上⾯的，如果开始节点是A ，环的⼊⼝是B ，相遇的节点是C ，那么</p>
<ul>
<li>慢指针⾛的距离是： S=AB+BC</li>
<li>快指针⾛的距离是： 假设多⾛了n圈，2S = AB+(BC+CB)*n+BC ，</li>
</ul>
<p>即 2(AB+BC) = AB+(BC+CB)*n+BC，也就是AB+BC = (BC+CB)*n</p>
<p>假设n =1 ，那么AB = CB ,也就是当前位置到环的⼊⼝的⻓度，等于链表头到环的⼊⼝的位置。</p>
<p>因此相遇之后，我们将⼀个快指针移动到链表头，两个指针每次⼀步，直到相遇，这个时候，相遇的节点就是环的⼊⼝节点。</p>
<pre><code class="language-java">public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode quick = pHead;
ListNode slow = pHead;
while (quick != null && slow.next != null) {
quick = quick.next;
slow = slow.next.next;
if (quick == slow) {
quick = pHead;
while (quick != slow) {
quick = quick.next;
slow = slow.next;
}
return quick;
}
}
return null;
}
</code></pre>
<ul>
<li>时间复杂度： O(n)</li>
<li>空间复杂度： O(1)</li>
</ul>
<h3 id="标记法破坏性解法">标记法（破坏性解法）</h3>
<p>通过修改节点结构来标记已访问的节点，适合可以修改链表的情况</p>
<pre><code class="language-java">public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) return null;
// 使用特殊值标记已访问节点
final int MARKER = Integer.MIN_VALUE;
ListNode current = head;
while (current != null) {
// 如果遇到标记值，说明是环的入口
if (current.val == MARKER) {
// 恢复原始值（可选）
return current;
}
// 标记当前节点
current.val = MARKER;
current = current.next;
}
return null;
}
/**
* 替代方案：使用额外字段进行标记（如果节点结构可扩展）
*/
static class MarkableListNode {
int val;
MarkableListNode next;
boolean visited;
MarkableListNode(int val) {
this.val = val;
this.visited = false;
}
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n) - 线性遍历</li>
<li>空间复杂度：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/19377779
頁:
[1]