[LintCode 题解] 腾讯面试算法题：带环链表 II

[hakunamatata11]

题目描述

给定一个链表，如果链表中存在环，则返回到链表中环的起始节点，如果没有环，返回 null。

样例 1:

输入：null,no cycle
输出：no cycle
解释：
链表为空，所以没有环存在。

样例 2:

输入：-21->10->4->5，tail connects to node index 1
输出：10
解释：
最后一个节点 5 指向下标为 1 的节点，也就是 10，所以环的入口为 10。

题解

考点：

• 双指针链表判环

题解：

• 使用双指针判断链表中是否有环，慢指针每次走一步，快指针每次走两步，若链表中有环，则两指针必定相遇。
• 假设环的长度为 l，环上入口距离链表头距离为 a，两指针第一次相遇处距离环入口为 b，则另一段环的长度为 c=l-b，由于快指针走过的距离是慢指针的两倍，则有 a+l+b=2*(a+b),又有 l=b+c，可得 a=c，故当判断有环时(slow==fast)时，移动头指针，同时移动慢指针，两指针相遇处即为环的入口。

算法面试高频题班免费试听，攻略还有更多大厂常考题型。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next==null) {
            return null;
        }

        ListNode fast, slow;
        fast = head.next;    		//快指针
        slow = head;				//慢指针
        while (fast != slow) {		//快慢指针相遇
            if(fast==null || fast.next==null)
                return null;
            fast = fast.next.next;
            slow = slow.next;
        } 

        while (head != slow.next) {  //同时移动 head 和慢指针
            head = head.next;
            slow = slow.next;
        }
        return head;				//两指针相遇处即为环的入口
    }
}