7<-6
（向下）v ^（向上）
1->2->3->4->5
如何判断链表是否有环，可以通过快慢指针的方式，比如 快一次走俩格，慢指针一次走一格，当存在环时，快慢指针最终会在环里相遇。
package algorithm;
public class Circle {
public static boolean isCycle(Node head) {
Node fastP = head;
Node slowP = head;
while(fastP!=null && fastP.next!=null){
if(fastP.val == slowP.val){
return true;
}
slowP=slowP.next;
fastP=fastP.next.next;
}
return false;
}
private static class Node{
private Integer val;
private Node next;
public Node(Integer val) {
this.val = val;
}
}
public static void main(String[] args) {
Node node1= new Node(5);
Node node2 = new Node(3);
Node node3 = new Node(7);
Node node4 = new Node(2);
Node node5 = new Node(6);
node1.next=node2;
node2.next=node3;
node3.next=node4;
node4.next=node5;
node5.next=node2;
System.out.println(isCycle(node1));
}
}
结果
true
Process finished with exit code 0
链表的环长是多少
如何计算环的长度，从快慢指针相遇开始，到下次相遇，他俩的速度差*前进的次数就是环长
package algorithm;
public class CycleLength {
public static Integer cycleLength(Node head) {
Node fastP = head;
Node slowP = head;
int len = 0;
int meetNumber = Integer.MAX_VALUE;
while (fastP != null && fastP.next != null) {
if (fastP.val == slowP.val && meetNumber!=Integer.MAX_VALUE) {
return len;
}
if (fastP.val == slowP.val ) {
meetNumber = fastP.val;
}
if(meetNumber!=Integer.MAX_VALUE){
len++;
}
slowP = slowP.next;
fastP = fastP.next.next;
}
return 0;
}
private static class Node {
private Integer val;
private Node next;
public Node(Integer val) {
this.val = val;
}
}
public static void main(String[] args) {
Node node1 = new Node(5);
Node node2 = new Node(3);
Node node3 = new Node(7);
Node node4 = new Node(2);
Node node5 = new Node(6);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node2;
System.out.println(cycleLength(node1));
}
}
结果
4
Process finished with exit code 0
链表环的入口结点
如果一个链表分为 入环长度 D,环内相遇点，慢指针走的长s1,快指针走的长s2,本题快指针速度是慢指针2倍，所以有公式
2(d+s1) = d+s1+n(s1+s2)
d=(n-1)(s1+s2)
无代码
以上时环形链表可能会遇到的三个典型问题，主要考察的是链表遍历以及对环的理解，至于其他链表操作，比如倒序遍历，双链比较排序等
不会，我可以学；落后，我可以追赶；跌倒，我可以站起来！