本文最后更新于2023年01月24日,已超过831天没有更新。如果文章内容或图片资源失效,请留言反馈,我会及时处理,谢谢!
您阅读这篇文章共耗时:
原理:我们先判断当前链表是否是环形链表,定位到快慢指针相遇的结点,这是创建一个temp指针指向第一个元素,用temp指针和慢指针继续遍历链表链表中环的入口结点,temp指针和慢指针相遇的结点就是环形链表的入口
数学分析:
为什么在快慢指针相遇之后链表中环的入口结点,用temp指针和慢指针去遍历链表时,相遇的结点就是环形链表的入口呢?
//找出循环链表的入口
public static Node getEntrance(Node first){
//判断链表是否有环
//定义两个快慢指针
Node fast=first;
Node slow=first;
Node temp=null;
//遍历链表,判断两指针是否相遇
while(slow!=null&&slow.next!=null){
fast=fast.next.next;
slow=slow.next;
//相遇,让新指针指向第一个结点,找到slow指针和temp指针相遇的结点,就是环的入口
if(fast.equals(slow)){
temp=first;
continue;
}
//是循环链表
if(temp!=null){
temp=temp.next;
//相遇了,找到了环的入口
if(slow.equals(temp)){
break;
}
}
}
//返回循环链表的入口
return temp;
}
测试代码:
package com.company.test;
/**
* @ProjectName [数据结构][5]实操
* @ClassName FastSlowTest
* @Description // 快慢指针,解决中间值问题
* @Email 2992794262@qq.com
* @Author ASUS
* @Date 2022/1/7
**/
public class CycleLinkEntranceTest {
public static void main(String[] args) {
Node first=new Node("aa",null);
Node second=new Node("bb",null);
Node third=new Node("cc",null);
Node fourth=new Node("dd",null);
Node fifth=new Node("ee",null);
Node sixth=new Node("ff",null);
Node seventh=new Node("gg",null);
first.next=second;
second.next=third;
third.next=fourth;
fourth.next=fifth;
fifth.next=sixth;
sixth.next=seventh;
//环形链表
seventh.next=third;
Node entrance = getEntrance(first);
System.out.println("环的入口是:"+entrance.item);
}
//找出循环链表的入口
public static Node getEntrance(Node first){
//判断链表是否有环
//定义两个快慢指针
Node fast=first;
Node slow=first;
Node temp=null;
//遍历链表,判断两指针是否相遇
while(slow!=null&&slow.next!=null){
fast=fast.next.next;
slow=slow.next;
//相遇,让新指针指向第一个结点,找到slow指针和temp指针相遇的结点,就是环的入口
if(fast.equals(slow)){
temp=first;
continue;
}
//是循环链表
if(temp!=null){
temp=temp.next;
//相遇了,找到了环的入口
if(slow.equals(temp)){
break;
}
}
}
//返回循环链表的入口
return temp;
}
private static class Node{
T item;
Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
}
本文来自投稿,不代表本站立场,如若转载,请注明出处:http://xuan.ddwoo.top/index.php/archives/916/