using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        var a = new LinkedListNode(6);

        var b = new LinkedListNode(5);

        var c = new LinkedListNode(2);

        var d = new LinkedListNode(1);

        a.Next = b;

        b.Next = c;

        c.Next = d;

        Console.WriteLine(ContainsCycle(a));

        Console.WriteLine(ContainsCycle1(a));

        Console.WriteLine("------------");

        var a2 = new LinkedListNode(6);

        var b2 = new LinkedListNode(5);

        var c2 = new LinkedListNode(2);

        var d2 = new LinkedListNode(1);

        a2.Next = b2;

        b2.Next = c2;

        c2.Next = a2;

        Console.WriteLine(ContainsCycle(a2));

        Console.WriteLine(ContainsCycle1(a2));

    }

    // Official answer. O(n) and O(1) time and space.

    public static bool ContainsCycle1(LinkedListNode root) {

        var slowRunner = root;

        var fastRunner = root;

        while(fastRunner != null && fastRunner.Next != null) {

            slowRunner = slowRunner.Next;

            fastRunner = fastRunner.Next.Next;

            if(fastRunner == slowRunner) {

                return true;

            }

        }

        return false;

    }

    // My attempt. O(n) space and time.

    public static bool ContainsCycle(LinkedListNode root) {

        Dictionary<LinkedListNode, bool> checkedNodes = new Dictionary<LinkedListNode, bool>();

        var current = root;

        bool contained = false;

        while (current != null) {

            checkedNodes.TryGetValue(current, out contained);

            if(contained) {

                return contained;   

            } else {

                checkedNodes.Add(current, true);

                current = current.Next;

            }

        }

        return false;   

    }

    public static void PrintList(LinkedListNode root) {

        Console.WriteLine(root.Value);

        var current = root;

        while(current.Next != null) {

            current = current.Next;

            Console.WriteLine(current.Value);

        }

    }

    public static void Delete(LinkedListNode root) {

        root.Value = root.Next.Value;

        root.Next = root.Next.Next;

        // Throw an exception if it's the last node in a list. 

        // Also, creates dangling nodes. (Nodes that aren't connected to anything.)

    }

}

​

public class LinkedListNode {

    public int Value { get; set; }

    public LinkedListNode Next { get; set; } 

​

    public LinkedListNode (int value) {

        Value = value;  

    }

}