Linked List Cycle Detection

LeetCode

Commonly asked at:Amazon Microsoft Bloomberg

Linked List Cycle Detection

Given a linked list, print true if it contains a cycle (some node's next eventually points back to an earlier node), false otherwise.

Example

Input: values 3 2 0 -4, cycle connects back to index 1 Output: true

Approach

Floyd's cycle detection ("tortoise and hare"): one pointer moves one step at a time, another moves two. If there's a cycle, the fast pointer will eventually lap the slow one and they'll meet inside the loop; if there's no cycle, the fast pointer simply reaches the end. This uses O(1) extra memory, unlike tracking visited nodes in a set.

Input format

Line 1: the list values, space-separated Line 2: the index the last node's next should connect back to, or -1 for no cycle

Print true or false.

Not solved yet

Ctrl+Enter

Editor

values = list(map(int, input().split()))
pos = int(input())
head = build_list(values)
if pos >= 0:
    nodes = []
    node = head
    while node:
        nodes.append(node)
        node = node.next
    nodes[-1].next = nodes[pos]
# TODO: Floyd's tortoise and hare — slow moves 1, fast moves 2
slow = fast = head

values = list(map(int, input().split()))
pos = int(input())
head = build_list(values)
if pos >= 0:
    nodes = []
    node = head
    while node:
        nodes.append(node)
        node = node.next
    nodes[-1].next = nodes[pos]
# TODO: Floyd's tortoise and hare — slow moves 1, fast moves 2
slow = fast = head

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Editor

values = list(map(int, input().split()))
pos = int(input())
head = build_list(values)
if pos >= 0:
    nodes = []
    node = head
    while node:
        nodes.append(node)
        node = node.next
    nodes[-1].next = nodes[pos]
# TODO: Floyd's tortoise and hare — slow moves 1, fast moves 2
slow = fast = head

values = list(map(int, input().split()))
pos = int(input())
head = build_list(values)
if pos >= 0:
    nodes = []
    node = head
    while node:
        nodes.append(node)
        node = node.next
    nodes[-1].next = nodes[pos]
# TODO: Floyd's tortoise and hare — slow moves 1, fast moves 2
slow = fast = head

Input (stdin)

Output

Run your code to see output here.

Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.

Community Discussions

No discussions yet

Be the first to start a conversation.