141. 环形链表及142.环形链表II.md

LeetCode 141. 环形链表及142.环形链表II

本题是要求判断一个单链表是否有环或者如果有环则找出环的起点。

141. 判断是否有环

判断是否有环很简单，给一个快指针和慢指针，同时从头指针head出发，如果有环则两个指针陷在环里必定会相遇。

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
  	public boolean hasCycle(ListNode head) {
      	ListNode fast, slow;
      	fast = slow = head;
      	
      	while (fast != null && fast.next != null) {
          	fast = fast.next.next;
          	slow = slow.next;
          
          	if (fast == slow)
              	return true;
        }
      	return false;
    }
}

找到环的起点

那么如何找到环的起点呢？这个比较巧妙。

首先和前面判断环一样，让快慢指针进入环并且第一次相遇，然后将慢指针（随意那个指针）置回起点，快指针和慢指针速度相同，那么当快慢指针再次相遇则必然是环的起点。

分析如下

在第一次相遇，假设slow走了k步，则fast走了2k步。由于是第1次相遇，则必然是slow进入环后，fast追击slow，并且fast比slow多走1圈，如下图，可得环的长度为k。


而如果再把slow放回head，让快指针再慢下来，则当slow进入环时，已经走了k-m步（不妨假设第一次相遇距离环的起点距离为m）。那么fast指针必定也走了k-m步，恰好走到了环的起点。

展开：寻找链表的中点

ListNode fast, slow;
fast = slow = head;

while (fast != null && fast.next != null) {
  	fast = fast.next.next;
  	slow = slow.next;
}
return slow; // 当链表长度为奇数2k+1时, slow恰好是正中间k，若为偶数2k时，则slow为k-1

寻找链表中点最大的作用是用于归并排序

扩展：寻找链表倒数第k个元素

ListNode fast, slow;
fast = slow = head;
for (int i = 0; i < k-1; i++)
  	fast = fast.next;
while (fast != null) {
  	fast = fast.next;
  	slow = slow.next;
}
return slow;