LeetCode 142. Linked List Cycle II

Problem

LeetCode 142. Linked List Cycle II

1. 题目简述

给出一个链表，判断链表是否存在环，如果有环，找出入环点，如果没有环，则返回null。例如：

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

2. 算法思路

极其经典的老题目，类似题目：LeetCode 141. Linked List Cycle

依然采用双指针做法，但是需要一些数学推导，由于markdown中不方便编辑公式，直接在纸上写以图片的形式说明算法。

双指针

两个指针，一个slow，一个fast，slow每次走一步，fast每次走两步，如果fast先到达null值，则说明无环；如果slow和fast相遇，则说明有环，我们记录相遇点。

时间复杂度:O(n).

空间复杂度:O(1)，只有fast和slow两个指针变量。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 数学推导过程记得写一下
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head, fast = head;

        ListNode cross = null;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow.equals(fast)) {
                cross = slow;
                break;
            }
        }

        if (cross == null) {
            return null;
        }

        // 有环，开始找环
        ListNode ptr1 = head, ptr2 = cross;
        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }

        // 注意，这里是返回的是ptr1或者ptr2
        return ptr1;
    }
}