142. 环形链表 II

leetcode链接：
https://leetcode.cn/problems/linked-list-cycle-ii/

方案一–迭代

将链表放到List中，然后判断其是否存在。

public class Solution {
    public ListNode detectCycle(ListNode head) {

        ArrayList<ListNode> list = new ArrayList<>();

        while (head != null) {
            if (list.contains(head)) {
                break;
            }
            list.add(head);
            head = head.next;
        }
        
        return head;
    }
}

Accepted

• 17/17 cases passed (257 ms)
• Your runtime beats 2.85 % of java submissions
• Your memory usage beats 27.16 % of java submissions (42.5 MB)

分析

时间复杂度：
O( n * n )
其中ArrayList.contains(head)的时间复杂度为n。

空间复杂度：
O( n )

方案二–快慢指针

快指针一次前进两格，慢指针一次前进一格子，当其相遇的时候，就说明是环形的

难点：判断有环之后，怎么找到开始入环的第一个节点。

解答参考：
https://leetcode.cn/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/

public class Solution {
    public ListNode detectCycle(ListNode head) {

        // 快慢指针

        // 先判断是否有环
        ListNode fast = head;
        ListNode slow = head;

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

            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                break;
            }
        }

        // 难点：判断有环之后，怎么找到开始入环的第一个节点。
        fast = head;

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

        return fast;
    }
}