链表是否存在环及其相干题目

1.链表中环相干题目

1.1 链表中是否有环

有一个单向链表，链表中有可能出现“环”，就像下图这样。 那么，如何用程序来判断该链表是否为有环链表呢？

思路

创建两个指针p1和p2（在Java里就是两个对象引用），让它们同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针p1每次向后移动1个节点，让指针p2每次向后移动2个节点，然后比力两个指针指向的节点是否雷同。假如雷同，则可以判断出链表有环，假如差别，则继承下一次循环。
类似于，小学奥数中的追及题目。此方法就类似于一个追及题目。 在一个环形跑道上，两个活动员从同一所在起跑，一个活动员速度快，另一个活动员速度慢。当两人跑了一段时间后，速度快的活动员必然会再次追上并超过速度慢的活动员，原因很简朴，因为跑道是环形的。 假设链表的节点数量为n，则该算法的时间复杂度为O(n)。除两个指针外，没有利用任何额外的存储空间，所以空间复杂度是O(1)。
1.2 求环长

假如链表有环，如何求出环的长度？
思路

当两个指针首次相遇，证实链表有环的时候，让两个指针从相遇点继承循环前进，并统计前进的循环次数，直到两个指针第2次相遇。此时，统计出来的前进次数就是环长。 因为指针p1每次走1步，指针p2每次走2步，两者的速度差是1步。当两个指针再次相遇时，p2比p1多走了整整1圈。 因此，环长 = 每一次速度差 × 前进次数 = 前进次数。
1.3 求入环节点

思路

上图是对有环链表所做的一个抽象示意图。假设从链表头节点到入环点的距离是D，从入环点到两个指针首次相遇点的距离是S1，从首次相遇点回到入环点的距离 是S2。
那么，当两个指针首次相遇时，各自所走的距离是多少呢？
指针p1一次只走1步，所走的距离是D+S1。 指针p2一次走2步，多走了n(n>=1)整圈，所走的距离是D+S1+n(S1+S2)。 由于p2的速度是p1的2倍，所以所走距离也是p1的2倍，因此： 2(D+S1) = D+S1+n(S1+S2) 等式经过整理得出：D = (n-1)(S1+S2)+S2。
也就是说，从链表头结点到入环点的距离，等于从首次相遇点绕环n-1圈再回到 入环点的距离。
这样一来，只要把其中一个指针放回到头节点位置，另一个指针保持在首次相遇点，两个指针都是每次向前走1步。那么，它们最终相遇的节点，就是入环节点。
1.4 具体代码

1. /**
2. * 链表是否存在环问题
3. */
4. public class LinkedListCycle {
6.     /**
7.      * 链表是否有环
8.      * @param head 链表的头节点
9.      */
10.     public static boolean hasCycle(Node head){
11.         Node p1 = head;
12.         Node p2 = head;
13.         while(p2 != null && p2.getNext().getNext() != null){
14.             p1 = p1.getNext();
15.             p2 = p2.getNext().getNext();
16.             if(p1 == p2)
17.                 return true;
18.         }
19.         return false;
20.     }
22.     /**
23.      * 统计链表中环的长度
24.      * @param head 链表的头节点
25.      * @return -1-代表链表中不存在环
26.      */
27.     public static int countCycleLength(Node head){
28.         if(!hasCycle(head))
29.             return -1;
30.         Node p1 = head;
31.         Node p2 = head;
32.         int count = 0;//记录循环次数
33.         int firstMeet = -1;//记录第一次相遇，循环的次数
34.         int secondMeet = -1;//记录第二次相遇，循环的次数
35.         while(true){
36.             p1 = p1.getNext();
37.             p2 = p2.getNext().getNext();
38.             if(p1 == p2 && firstMeet != -1)//第二次相遇
39.                 secondMeet = count;
40.             if(p1 == p2 && firstMeet == -1)//第一次相遇，为firstMeet赋值
41.                 firstMeet = count;
42.             if(firstMeet != -1 && secondMeet != -1)//统计出第一次和第二次相遇的循环次数后，可以结束循环了
43.                 break;
44.             count++;
45.         }
46.         return secondMeet - firstMeet;
47.     }
49.     /**
50.      * 获取入环节点
51.      * @param head 链表头节点
52.      * @return null-代表链表中不存在环
53.      */
54.     public static Node getEnterCycleNode(Node head){
55.         if(!hasCycle(head))
56.             return null;
57.         Node p1 = head;
58.         Node p2 = head;
59.         Node firstMeetNode = null;
60.         while(true){
61.             p1 = p1.getNext();
62.             p2 = p2.getNext().getNext();
63.             if(p1 == p2){
64.                 firstMeetNode = p1;
65.                 break;
66.             }
67.         }
68.         p1 = head;
69.         p2 = firstMeetNode;
71.         Node enterCycleNode = null;
72.         while(true){
73.             p1 = p1.getNext();
74.             p2 = p2.getNext();
75.             if(p1 == p2){
76.                 enterCycleNode = p2;
77.                 break;
78.             }
79.         }
80.         return enterCycleNode;
81.     }
84.     private static class Node{
85.         int data;
86.         Node next;
87.         Node(int data){
88.             this.data = data;
89.         }
91.         public int getData() {
92.             return data;
93.         }
95.         public Node getNext() {
96.             return next;
97.         }
98.     }
100.     public static void main(String[] args) {
101.         Node node1 = new Node(1);
102.         Node node2 = new Node(2);
103.         Node node3 = new Node(3);
104.         Node node4 = new Node(4);
105.         Node node5 = new Node(5);
107.         node1.next = node2;
108.         node2.next = node3;
109.         node3.next = node4;
110.         node4.next = node5;
111.         node5.next = node2;
113.         System.out.println(hasCycle(node1));//true
114.         System.out.println(countCycleLength(node1));//4
115.         System.out.println(getEnterCycleNode(node1).getData());//2
116.     }
117. }

复制代码

只是为了记录自己的学习历程，且本人水平有限，不对之处，请指正。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。