LeetCode: Linked List Cycle 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;
        }
    }
}
Performance

You have implemented Floyd’s Cycle-Finding Algorithm which adheres to \$0(1)\$ storage space. An alternative exists Brent’s Cycle Detection Algorithm which uses the same storage space. Check out this review on Computer Science SE for a comparison. It appears in general, Brent's algorithm is faster.


  According to Brent's paper, the complexity of Floyd's algorithm is between 3max(m,n) and 3(m+n), and that of Brent's is at most
  2max(m,n)+n, which is always better than 3max(m,n).


courtesy of Yuval Filmus' answer at CS

Style Guidelines


use var to declare a variable, specially when the type can be inferred from code
use a separate line for declaring attributes on top of members
use a white space after a method name and the opening parenthesis
use a white space after the while statement
use white space around operators (!=)
remove redundant nested else branches if the if branch always performs a return