判断一个单链表是否存在环，如果存在返回入环节点
时间复杂度O(N)，空间复杂度O(1)
快慢指针：从头结点开始，快指针一次走两步，满指针一次走一步，如果这两个指针相遇后，快指针回到头结点，两个指针一起开始走，每次走一步，再次相遇的节点即是入环节点
package com.jiucaiyuan.net.algrithm.linked;
import java.util.HashSet;
import java.util.Set;
/**
* 【问题】：判断一个单链表是否存在环，如果存在返回入环节点
* 【方法】快慢指针：从头结点开始，快指针一次走两步，满指针一次走一步，
* 如果这两个指针相遇后，快指针回到头结点，两个指针一起开始走，
* 每次走一步，再次相遇的节点即是入环节点
*
* @Author jiucaiyuan 2022/4/7 23:12
* @mail services@jiucaiyuan.net
*/
public class FindLoopNode {
/**
* 确实简洁
* @param head
* @return
*/
public static ListNode getLoopNode(ListNode head){
if(head == null || head.next == null || head.next.next == null){
return null;
}
ListNode n1 = head.next;
ListNode n2 = head.next.next;
while(n1!= n2) {
if (n2.next == null || n2.next.next == null) {
return null;
}
n1 = n1.next;
n2 = n2.next.next;
}
n2 = head;
while (n1 != n2){
n1 = n1.next;
n2 = n2.next.next;
}
return n1;
}
public static ListNode entryNodeOfLoop(ListNode pHead) {
if (pHead == null) {
return null;
}
ListNode fast = pHead;
ListNode low = pHead;
boolean second = false;
while (low != null && fast != null && fast.next != null) {
if (fast == low) {
if (second) {
return fast;
}
if (fast != pHead && low != pHead) {
fast = pHead;
second = true;
continue;
}
}
low = low.next;
if (second) {
fast = fast.next;
} else {
fast = fast.next.next;
}
}
//如果快慢指针有一个为null，则不存在环
return null;
}
public static void print(ListNode head) {
Set<ListNode> set = new HashSet<>();
System.out.println("-------------------------");
while (head != null) {
if(!set.contains(head)){
set.add(head);
}else{
System.out.print("\t入环节点="+head.val);
break;
}
System.out.print("\t"+head.val);
head = head.next;
}
System.out.println();
System.out.println("-------------------------");
}
public static void main(String[] args) {
int[] arrays = {1, 2, 3, 4, 15,20,21,43,25,8,5,40};
int entryNodeValue = 21;
// int[] arrays = {0};
ListNode head = new ListNode(arrays[0]);
ListNode tail = null;
ListNode entryNode = null;
if (arrays.length > 1) {
ListNode tmp = new ListNode(arrays[1]);
head.next = tmp;
for (int i = 2; i < arrays.length; i++) {
tail = new ListNode(arrays[i]);
if (arrays[i] == entryNodeValue) {
entryNode = tail;
}
tmp.next = tail;
tmp = tmp.next;
}
}
tail.next = entryNode;
print(head);
System.out.println("找到的入环节点是："+entryNodeOfLoop(head));
}
}
输出结果
-------------------------
1 2 3 4 15 20 21 43 25 8 5 40 入环节点=21
-------------------------
找到的入环节点是：ListNode{val=21}
Process finished with exit code 0