Linked List Cycle II

Question

• Leetcode: Linked List Cycle II

• Lintcode: Linked List Cycle II

Description

Given a linked list, return the node where the cycle begins.

If there is no cycle, returnnull.

Example

Given-21->10->4->5, tail connects to node index 1，return10

Challenge

Follow up:

Can you solve it without using extra space?

题解思路

可以先判断Linked List是否有Cycle，利用two pointers可以很快得到。接下来就要分析，快慢指针第一次相遇时，位置、步数和环的关系。

    a            b
A ------ B --------+
         |         |
       c |         |
         +-------- C



* A: 起始点
* B: Cycle Begins
* C: 1st 快慢指针相遇点


* A->B: a
* B->C: b
* C->B: c
* 环的长度 (b+c) 为 R

第一次相遇时，慢指针所走步数为

a + b

快指针走的步数为

a + b + nR

我们知道快指针是慢指针速度的2倍，因此

2(a + b) = a + b + nR

那么

a + b = nR

同时

b + c = R

所以

a = (n - 1)R + c;

也就是说，从A点和C点同时出发，以相同的速度前进，那么下一次相遇的位置将是B。

参考 LeetCode: https://leetcode.com/articles/linked-list-cycle/

源代码

Easier to understand:

/**
 * 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;
        ListNode fast = head;
        while (slow != null && fast != null) {
            slow = slow.next;
            if (fast.next == null) return null;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        slow = head;
        if (fast != null) {
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
        return null;
    }
}

Preferred Implementation:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    private ListNode answer = null;
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null) {

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

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

Harder to understand with pointer corner cases

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
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.next;
            slow = slow.next;
        }
        return head;
    }
}