Challenge

https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/773/

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.

Follow up

• Can you solve it using \$O(1)\$ (i.e. constant) memory?
• Can you please review about performance?

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace LinkedListQuestions
{
 public class ListNode
    {
        public int val;
        public ListNode next;

        public ListNode(int x)
        {
            val = x;
        }
    }

    [TestClass]
    public class HasCycleTest
    {
        [TestMethod]
        public void HasCycle()
        {
            ListNode head = new ListNode(3);
            head.next = new ListNode(2);
            head.next.next = new ListNode(0);
            head.next.next.next = new ListNode(-4);
            head.next.next.next.next = head.next; //2
            Assert.IsTrue(HasCycleClass.HasCycle(head));
        }

        [TestMethod] public void NoCycle()
        {
            ListNode head = new ListNode(3);
            head.next = new ListNode(2);
            head.next.next = new ListNode(0);
            Assert.IsFalse(HasCycleClass.HasCycle(head));
        }

        [TestMethod]
        public void OneItem()
        {
            ListNode head = new ListNode(3);
            Assert.IsFalse(HasCycleClass.HasCycle(head));
        }
    }

    public class HasCycleClass
    {
        public static bool HasCycle(ListNode head)
        {
            if (head == null || head.next == null)
            {
                return false;
            }
            ListNode slow = head.next;
            ListNode fast = head.next.next;
            while(fast!= null)
            {
                if (fast == slow)
                {
                    return true;
                }
                else
                {
                    slow = slow.next;
                    if (fast.next == null)
                    {
                        return false;
                    }
                    fast = fast.next.next;
                }
            }

            return false;
        }
    }
}