判断链表中的环Floyd
2018-12-08 本文已影响21人
ab029ac3022b
问题源于 leetcode 中的一道题:
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
就比方说下面这个图，就是返回那个红色的点
链表的数据结构：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
算法介绍
- 先定义两个指针，一个叫 fast，一个叫 slow，都指向链表中的第一个节点，
- fast 一次向前走两步(fast = fast.next.next)，slow 一次走一步 (slow = slow.next)
- 如果这个链表中有环，那 slow 和 fast 一定会在环中的某处相遇
- 记录 slow 走过的路程为 x ，那么 fast 走过的路程就是 2x，即为 slow 再走 x 就能回到自己的位置
- 再把 x 分成 y + z ，y 表示从起始点到红点的路程，z 表示从红点到相遇点 slow 走过的路程，z 不好在图中表示
- 然后就得出了这样一个结论：slow 如果在相遇点处，再走个 y + z 就可以再回到这个相遇点处，slow 如果在红点处，走个 z 就能到相遇点处。一定要理解这句话
- 根据上面这个结论，可以得出：1. slow 在相遇点处，再走个 y 就能到红点处。2. 再往链表的起始点处创一个指针 slow2，则这个指针走 y 的路程，可到达红点处
- 让 slow2 和 slow 同时开始走(slow2 = slow2.next; slow = slow.next;)， 它们相遇的地方，就是红点
算法代码
public class Solution {
//这里给出的是链表的头节点
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
ListNode slow2 = head;
while (slow2 != slow){
slow = slow.next;
slow2 = slow2.next;
}
return slow;
}
}
return null;
}
}
