LeetCode 142. Linked List Cycle

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

说明：不允许修改给定的链表。

进阶：
你是否可以不用额外空间解决此题？

注意:

本题以记录为主,思路和解法参考大神博客,点击 这里

思路:

• 典型的考验快慢双指针的问题
• 难点在于获取环链的入口节点

代码:

    public ListNode detectCycle( ListNode head ) {
            if( head == null || head.next == null ){
                return null;
            }
            ListNode fp = head, sp = head;
            while( fp != null && fp.next != null){
                sp = sp.next;
                fp = fp.next.next;
                //判断是否成环
                if( fp == sp ){  
                    break;
                }
            }
            if( fp == null || fp.next == null ){
                return null;
            }
            //fp到环入口距离 = head到环入口距离
            sp = head;
            while( fp != sp ){
                sp = sp.next;
                fp = fp.next;
            }
            return sp;
    }

总结:

1. 快慢双指针判环问题:可以看做环形跑道赛跑者,领先者速度为每单位时间两格,落后者速度为每单位时间一格
   两位跑者进入环道时,相对速度为一格,所以领先者总能在第一次套圈前与落后者相遇
   若设置领先者速度是落后者三倍及以上,可能会发生套圈单并不相遇的情况
   2.关于fp到环入口距离与head到环入口距离相等这一结论,点击这里阅读研究大神解答,
   3.快慢指针方法仅限于环形数据结构,但由于其优秀的遍历效率,在处理数组等问题时,可以自行将首尾节点相连,借用快慢指针来进行各种比较与判断
   4.轻喷