习惯github pages风格的请看我的另一篇博客
题目23：链表中环的入口节点
如果一个链表中包含环，请找出该链表的环的入口结点。
举例说明
如：在1->2->3->4->5->6->3的链表中，包含一个环，环的入口节点是3。
解法
1. 哈希表
遍历整个链表，并将链表结点存入哈希表中，如果遍历到某个链表结点已存在，那么该点即为环的入口结点
2. 断开链表法
前后两个指针，破坏他们之间的链接，修改链表。
但是这个方法会破坏链表结构。
代码
public class _23 {
private static class ListNode {
private int val;
private ListNode next;
public ListNode() {
};
public ListNode(int value) {
this.val = value;
}
}
public static ListNode meetingNode(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head;
ListNode fast = head.next;
if (fast == null) {
return null;
}//断开遍历过的链表
while (fast != null) {
slow.next = null;
slow = fast;
fast = fast.next;
}
return slow;
}
public static void main(String[] args) {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
ListNode n6 = new ListNode(6);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n3;
System.out.println(meetingNode(n1).val);
}
}
输出
断开链表法
3. 快慢指针法
- 确定链表中是否包含环：双指针，一个每次移动一步，一个每次移动两步，如果两个指针最后相遇，那么就包含环。（注意，移动两步的指针要判断判断其第一步不为空，才能移动第二步）
- 确定环中点节点数目：在上面相遇的节点的基础上，移动一个指针，并计数，当指针回到该节点时，确定环中节点数目。
- 找到环的入口节点：从头开始，使用两个指针，第一个指针先移动n步（其中n为确定的环中的节点数目），第二个指针再开始同时同速移动，两个指针相遇的节点即为入口节点。
不用计算环节点数的快慢指针法
如果链表存在环，我们无需计算环的长度n，只需在相遇时，让一个指针在相遇点出发，另一个指针在链表首部出发，然后两个同时同速移动，它们相遇点就是环的入口处。
参考文章
牛客网讨论区
有部分整理和修改
推导
快慢指针法
- 条件
假设x为环前面的路程（黑色路程），a为环入口到相遇点的路程（蓝色路程，假设顺时针走）， c为环的长度（蓝色+橙色路程） - 相遇的时候
- 从环的角度--路程差
慢指针走的路程为 Sslow = x + m * c + a
快指针走的路程为 Sfast = x + n * c + a - 从速度（2 *）与时间（一样）角度--路程差
2 Sslow = Sfast - 联立方程
2 * ( x + m*c + a ) = (x + n c + a)
从而可以推导出：
x = (n - 2 * m )c - a
= (n - 2 m -1 )c + c - a
- 从环的角度--路程差
- 即环前面的路程 = 数个环的长度（可能为0） + c - a
什么是c - a？这是相遇点后，环后面部分的路程。（橙色路程） - 所以，我们可以让一个指针从起点A开始走，让一个指针从相遇点B开始继续往后走，
2个指针速度一样，那么，当从原点的指针走到环入口点的时候（此时刚好走了x）
从相遇点开始走的那个指针也一定刚好到达环入口点。
所以2者会相遇，且恰好相遇在环的入口点。 - 最后，判断是否有环，且找环的算法复杂度为：
时间复杂度：O(n)
空间复杂度：O(1)
代码
public class _23 {
private static class ListNode {
private int val;
private ListNode next;
public ListNode() {
};
public ListNode(int value) {
this.val = value;
}
}
public static ListNode meetingNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
// 链表中没有环
if (fast == null || fast.next == null) {
return null;
}
//有环， slow从头结点开始，fast从相遇点开始
slow = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
public static void main(String[] args) {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
ListNode n6 = new ListNode(6);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n3;
System.out.println(meetingNode(n1).val);
}
}
输出
快慢指针法
