Linked List Cycle

Given a linked list with potentially a loop, determine whether the linked list from the first node contains a cycle in it. For bonus points, do this with constant space.

Parameters

  • nodes: The first node of a linked list with potentially a loop.

Result

  • Whether there is a loop contained in the linked list.

Examples

Example 1

Input:

Output:

true

Example 2

Input:

Output:

false

Constraints

  • 1 <= len(nodes) <= 10^5

Try it yourself

Solution

If a linked list has no loop, then when we iterate through the list, we will eventually reach the end of the list, at which point we can simply return. However, the challenge is figuring out how to terminate the program if it finds a loop. Otherwise the program would go on forever.

A simple solution would be to use a set to store the information. We store all the nodes we have been through and check if we have been there each time we move. However, a set is not constant memory, and there might be issues with hashing and whatnot. Clearly there is a better way.

Introducing Floyd's Cycle Finding Algorithm, also known as the Tortoise and Hare Algorithm. The idea is to have two pointers, the fast pointer (or "hare") moves at double speed of the slow pointer (or "tortoise"). Each cycle, the tortoise moves once and the hare moves twice. The idea is that since the cycle must have integer size, when the tortoise and the hare are both in the cycle, their distance difference must also be an integer. Then, each cycle, because of their speed difference, the distance between them constantly reduces until they meet, in which case we know there is a cycle. However, if there is no cycle, they will never meet because the speed of the hare is always faster.

Time Complexity: O(n)

Technically O(n/2) but again we factor out the constant and we are left with linear time. Worst case we have, O(2n) as the small pointer moves around the entire array once. Either way we have O(n) time complexity.

This is a graphics that explains the idea:

First slide
First slide
First slide
First slide

Below is an implementation.

1class Node:
2    def __init__(self, val, next=None):
3        self.val = val
4        self.next = next
5
6def node_next(node):
7    return node.next or node
8
9def has_cycle(nodes: Node) -> bool:
10    tortoise = node_next(nodes)
11    hare = node_next(node_next(nodes))
12    while tortoise != hare and hare.next is not None:
13        tortoise = node_next(tortoise)
14        hare = node_next(node_next(hare))
15    return hare.next is not None
16
17if __name__ == '__main__':
18    raw_input = [int(x) for x in input().split()]
19    nodes_list = []
20    for i, entry in enumerate(raw_input):
21        nodes_list.append(Node(i))
22    for i, entry in enumerate(raw_input):
23        if entry != -1:
24            nodes_list[i].next = nodes_list[entry]
25    nodes = nodes_list[0]
26    res = has_cycle(nodes)
27    print('true' if res else 'false')
28
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4import java.util.Scanner;
5import java.util.stream.Collectors;
6
7class Solution {
8    public static class Node<T> {
9        public T val;
10        public Node<T> next;
11
12        public Node(T val) {
13            this(val, null);
14        }
15
16        public Node(T val, Node<T> next) {
17            this.val = val;
18            this.next = next;
19        }
20    }
21
22    public static Node<Integer> nextNode(Node<Integer> node) {
23        if (node.next == null) {
24            return node;
25        }
26        return node.next;
27    }
28
29    public static boolean hasCycle(Node<Integer> nodes) {
30        Node<Integer> tortoise = nextNode(nodes);
31        Node<Integer> hare = nextNode(nextNode(nodes));
32        while (tortoise != hare && hare.next != null) {
33            tortoise = nextNode(tortoise);
34            hare = nextNode(nextNode(hare));
35        }
36        return hare.next != null;
37    }
38
39    public static List<String> splitWords(String s) {
40        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
41    }
42
43    public static void main(String[] args) {
44        Scanner scanner = new Scanner(System.in);
45        List<Integer> rawInput = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
46        ArrayList<Node<Integer>> nodesList = new ArrayList<>();
47        for (int i = 0; i < rawInput.size(); i++) {
48            nodesList.add(new Node<Integer>(i));
49        }
50        for (int i = 0; i < rawInput.size(); i++) {
51            if (rawInput.get(i) != -1) {
52                nodesList.get(i).next = nodesList.get(rawInput.get(i));
53            }
54        }
55        Node<Integer> nodes = nodesList.get(0);
56        scanner.close();
57        boolean res = hasCycle(nodes);
58        System.out.println(res);
59    }
60}
61
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5class Solution
6{
7    public class Node<T> 
8    {
9        public T val;
10        public Node<T> next;
11
12        public Node(T val) 
13        {
14            this.val = val;
15        }
16
17        public Node(T val, Node<T> next) 
18        {
19            this.val = val;
20            this.next = next;
21        }
22    }
23
24    public static Node<int> NextNode(Node<int> node) {
25        if (node.next == null) {
26            return node;
27        }
28        return node.next;
29    }
30
31    public static bool HasCycle(Node<int> nodes) {
32        Node<int> tortoise = NextNode(nodes);
33        Node<int> hare = NextNode(NextNode(nodes));
34        while (tortoise != hare && hare.next != null) {
35            tortoise = NextNode(tortoise);
36            hare = NextNode(NextNode(hare));
37        }
38        return hare.next != null;
39    }
40
41    public static List<string> SplitWords(string s)
42    {
43      return string.IsNullOrEmpty(s) ? new List<string>() : s.Trim().Split(' ').ToList();
44    }
45
46    public static void Main()
47    {
48        List<int> rawInput = SplitWords(Console.ReadLine()).Select(int.Parse).ToList();
49        List<Node<int>> nodesList = new List<Node<int>>();
50        for (int i = 0; i < rawInput.Count; i++) 
51        {
52            nodesList.Add(new Node<int>(i));
53        }
54        for (int i = 0; i < rawInput.Count; i++) 
55        {
56            if (rawInput[i] != -1) 
57            {
58                nodesList[i].next = nodesList[rawInput[i]];
59            }
60        }
61        Node<int> nodes = nodesList[0];
62        bool res = HasCycle(nodes);
63        Console.WriteLine(res ? "true" : "false");
64    }
65}
66
1class Node {
2    constructor(val, next = null) {
3        this.val = val;
4        this.next = next;
5    }
6}
7
8function nextNode(node) {
9    if (node.next == null) return node;
10    return node.next;
11}
12
13function hasCycle(nodes) {
14    let tortoise = nextNode(nodes);
15    let hare = nextNode(nextNode(nodes));
16    while (tortoise !== hare && hare.next != null) {
17        tortoise = nextNode(tortoise);
18        hare = nextNode(nextNode(hare));
19    }
20    return hare.next != null;
21}
22
23function splitWords(s) {
24    return s == "" ? [] : s.split(' ');
25}
26
27function* main() {
28    const raw_input = splitWords(yield).map((v) => parseInt(v));
29    const nodes_list = [];
30    for (let i = 0; i < raw_input.length; i++) {
31        nodes_list.push(new Node(i));
32    }
33    for (let i = 0; i < raw_input.length; i++) {
34        if (raw_input[i] != -1) {
35            nodes_list[i].next = nodes_list[raw_input[i]];
36        }
37    }
38    const nodes = nodes_list[0];
39    const res = hasCycle(nodes);
40    console.log(res);
41}
42
43class EOFError extends Error {}
44{
45    const gen = main();
46    const next = (line) => gen.next(line).done && process.exit();
47    let buf = '';
48    next();
49    process.stdin.setEncoding('utf8');
50    process.stdin.on('data', (data) => {
51        const lines = (buf + data).split('\n');
52        buf = lines.pop();
53        lines.forEach(next);
54    });
55    process.stdin.on('end', () => {
56        buf && next(buf);
57        gen.throw(new EOFError());
58    });
59}
60
1#include <algorithm> // copy
2#include <iostream> // boolalpha, cin, cout
3#include <iterator> // back_inserter, istream_iterator
4#include <sstream> // istringstream
5#include <string> // getline, string
6#include <vector> // vector
7
8template <typename T>
9struct Node {
10    T val;
11    Node<T>* next;
12
13    explicit Node(T val, Node<T>* next = nullptr)
14        : val{val}, next{next} {}
15
16    ~Node() {
17        delete next;
18    }
19};
20
21Node<int>* next_node(Node<int>* node) {
22    if (node->next == NULL) {
23        return node;
24    }
25    return node->next;
26}
27
28bool has_cycle(Node<int>* nodes) {
29    Node<int>* tortoise = next_node(nodes);
30    Node<int>* hare = next_node(next_node(nodes));
31    while (tortoise != hare && hare->next != NULL) {
32        tortoise = next_node(tortoise);
33        hare = next_node(next_node(hare));
34    }
35    return hare->next != NULL;
36}
37
38template<typename T>
39std::vector<T> get_words() {
40    std::string line;
41    std::getline(std::cin, line);
42    std::istringstream ss{line};
43    std::vector<T> v;
44    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
45    return v;
46}
47
48int main() {
49    std::vector<int> rawInput = get_words<int>();
50    std::vector<Node<int>*> nodeList;
51    for (int i = 0; i < rawInput.size(); i++) {
52        nodeList.push_back(new Node<int>(i));
53    }
54    for (int i = 0; i < rawInput.size(); i++) {
55        if (rawInput[i] != -1) {
56            nodeList[i]->next = nodeList[rawInput[i]];
57        }
58    }
59    Node<int>* nodes = nodeList[0];
60    bool res = has_cycle(nodes);
61    std::cout << std::boolalpha << res << '\n';
62}
63