Linked List Cycle II

https://leetcode.com/problems/linked-list-cycle-ii/
给定一个链表，判断这个链表是否有环，如果有环，返回环的起始位置

常规判断链表是否有环的方法，快慢指针，如果相遇，表明有环，很好理解
本题做了升华，找到有环的链表起点

解法1：暴力Set

给一个HashSet，只要走过的链表，就存进set，一个指针遍历链表，如果发现对应的node再Set中，就找到了起点，反之什么都没找到
talk is cheap，直接上代码吧~

//额外存储大法
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> se = new HashSet<ListNode>();
        ListNode tmp = head;
        se.add(tmp);
        while (tmp != null && tmp.next != null) {
            tmp = tmp.next;
            if (se.contains(tmp)) {
                return tmp;
            }
            se.add(tmp);
        }
        return null;
    }

解法2

本题其实有个附属条件，就是不要增加额外的存储空间，也就是用O(1)的存储空间
上图

image.png

• Node的起点到环开始的长度是a
• 环的长度是c
• 环的起点到fast和slow相遇的点长度是x
• slow 和fast 相遇，slow走过的长度是s， 那么fast走过的长度，一定是2s（因为fast每走两步，slow走一步）
• 我们可以得到以下等式

2s = nc + s (fast走了2s，slow走过了s，而fast一定比slow多走至少1圈，所以用n表示)
s = a + x(slow走过的s，就是a+x)

合并后nc = a + x
变换一下  得到  a = (n-1) c + c-x 
c-x的含义就是从相遇的点继续往下走到环开始点的距离
（n-1） 代表多走的环长

• 所以，从slow 和fast相遇的点开始一个p，从链表头开始一个q，每次都走一步，那么它们一定会在环开始的入口处相遇
  上代码

 public ListNode detectCycle2(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }

        if (fast == null || fast.next == null) {
            return null;
        }

        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

参考文章：https://www.cnblogs.com/springfor/p/3862125.html