Linked List Cycle

ID: 141; easy

Linked List Cycle - LeetCodeLeetCode

LintCode 炼码 - 更高效的学习体验！www.lintcode.com

Solution 1 (Go)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    m := make(map[*ListNode]bool)
    for head != nil {
        if _,found := m[head]; found {
            return true
        }
        m[head] = true
        head = head.Next
    }
    return false
}

Solution 2 (Go)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    tortoise, hare := head, head
    for tortoise != nil && hare != nil && hare.Next != nil {
        tortoise = tortoise.Next
        hare = hare.Next.Next
        if tortoise == hare {
            return true
        }
    }
    return false
    
}

Solution 3 (Java)

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null)
            return false;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }

        return false;
    }
}

Floyd's tortoise and hare cycle-finding algorithm

Cycle detectionWikipedia

The tortoise move by 1 step each time and the hare moves by 2 steps at a time. If there is a cycle, the hare will eventually catch the tortoise at a position.

A simple idea of the proof can be tracking the gap between the tortoise and the hare. By construction, the gap increases by 1 each iteration. Eventually, the gap with become n, where n is the number of elements in the cycle (not the whole list). This is the time when the tortoise and the hare meet. More proofs:

Proof of Floyd Cycle Chasing (Tortoise and Hare)Mathematics Stack Exchange