141. Linked List Cycle

输入输出

Given a linked list, determine if it has a cycle in it.

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

答案一

public boolean hasCycle(ListNode head) {
    if(head==null) return false;
    ListNode walker = head;
    ListNode runner = head;
    while(runner.next!=null && runner.next.next!=null) {
        walker = walker.next;
        runner = runner.next.next;
        if(walker==runner) return true;
    }
    return false;
}

图文详解

• Use two pointers, walker and runner.
• walker moves step by step. runner moves two steps at time (每次移动两步).
• if the Linked List has a cycle walker and runner will meet at some point (在某个点相遇).

参考

O(1) Space Solution