看linked list是否有cycle的问题,并且要求不用多余的memory space。
方法:使用两个pointer,一个走的快(每次进两步)另一个走的慢(每次走一步),如果存在cycle的话,两个pointer最终会相遇。

注意:要检查head pointer是否是null,另外每次走两个的pointer需要检查每一次advance是否是null,不然会出exception

Code如下:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode next1, next2;
        if (head == null)
            return false;
        else
        {
            next1 = head.next;
            next2 = head.next;
            if (next2 == null) // check to make sure not to step into a null pointer
                return false;
            next2 = next2.next;
            while(next1 != null && next2 != null)
            {
                if (next1 == next2)// if two pointer met, then cycle exist
                    return true;
                else
                {
                    next1 = next1.next;
                    next2 = next2.next;
                    if (next2 == null)
                        break;
                    else
                        next2 = next2.next;
                }
            }
            return false;
        }
    }
}

follow up问题:如果发现cycle,怎样找到这个cycle的位置呢?
首先假设两个指针都从起点开始,在黄色点相遇:
figure-1

figure-2
x:初始点到红点的距离, y:红点到黄点(图中右方外圈)的距离,z:黄点再到红点的距离(下图中左边内圈)
figure-3
那么我们知道S从初始到黄点一共走了x+y的距离,而F从初始到黄点除了走x+y的距离,还多走了一个圈,就是x+y+z+y的距离。
而我们知道F是S速度的两倍,所以任何时候F走过的距离都是S的两倍,所以2(x+y)=x+z+2y, 所以我们可以得到x=z (观察非常敏锐:))
所以要得到cycle开始的位置,在S和F相遇之后,S继续前进,F移动到LinkedList开头,每次同时前进一步,直到两者相遇就是cycle的开始
figure-4

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

用以上方法写出代码

LinkedListCycle II: One thing to notice is that the slow needs to go first for the above arguments to hold. Otherwise the fast will meet slow one cycle before. So the code should be

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

汗,第一次的代码实在太ugly了,重新写过,算法是一样的LinkedListCycleI

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            fast = fast.next;
            if (fast == slow)
                return true;
            if (fast == null)
                break;
            slow = slow.next;
            fast = fast.next;
            if (fast == slow)
                return true;
        }
        return false;
    }
}

Simplify further, only check equalization once.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null) {
            fast = fast.next;
            if (fast == null)
                break;
            //only need to check here, if fast != slow, then fast.next != slow.next;
            if (fast == slow)
                return true;
            fast = fast.next;
            slow = slow.next;
        }
        return false;
    }
}

Linked List Cycle I/II

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s