1.题目--判断链表是否成环
已经了解了快慢指针的应用原理，引申：用快慢指针去判断链表是否成环。
题解
简而言之，在fast和slow指针遍历的这种情况下，如果链表是成环的，那么在循环遍历了两次后，fast指针就会和slow指针相遇。
所以只需要判断两者是否能够相遇，就知道是否成环。
public static boolean IsCircle(Node head) {
Node slow = head;
Node fast = head;
// 检测环的存在
while (fast != null && fast.next != null) {
slow = slow.next; // 慢指针每次移动一步
fast = fast.next.next; // 快指针每次移动两步
if (slow == fast) {
return true; //只要能相遇，就能确定为环
}
}
return false;
}通过main函数检验正确性：
①手动成环后
public class Main {
public static void main(String[] args) {
Node node1=new Node(1);
Node node2=new Node(2);
Node node3=new Node(3);
Node node4=new Node(4);
Node node5=new Node(5);
node1.next=node2;
node2.next=node3;
node3.next=node4;
node4.next=node5;
node5.next=node1;//手动成环
// System.out.println(Test1116.mid(node1));
// System.out.println(node1.toString());
System.out.println(Test1116.IsCircle(node1));
}
}
结果:
②手动不成环
public class Main {
public static void main(String[] args) {
Node node1=new Node(1);
Node node2=new Node(2);
Node node3=new Node(3);
Node node4=new Node(4);
Node node5=new Node(5);
node1.next=node2;
node2.next=node3;
node3.next=node4;
node4.next=node5;
node5.next=null;//手动不成环
// System.out.println(Test1116.mid(node1));
// System.out.println(node1.toString());
System.out.println(Test1116.IsCircle(node1));
}
}结果：
2.题目--判断成环后，找到链表的起始点
判断成环后，那么找到成环时链表的起点。
题解:
public static int CircleNode(Node head) {
if (head == null || head.next == null) {
// 如果链表为空或只有一个节点，那么它肯定没有环
return 0; // 或者可以抛出一个异常，表示输入无效
}
Node slow = head;
Node fast = head;
// 检测环的存在
while (fast != null && fast.next != null) {
slow = slow.next; // 慢指针每次移动一步
fast = fast.next.next; // 快指针每次移动两步
if (slow == fast) {
// 一旦快慢指针相遇，说明存在环
// 将慢指针重新指向头节点，快指针保持不变（它已经在环内了）
slow = head;
// 然后同时移动快慢指针，每次只移动一步，直到它们再次相遇
// 相遇的点就是环的起始节点
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
// 返回环起始节点的数据
return slow.data;
}
}
// 如果没有检测到环，则返回0
return 0;
}验证后得到结果：1
