LeetCode: Linked List Cycle

Question

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;
        }
    }
}

Answer 1

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

Answer 2

I have some style and organization comments to add to @dfhwze 's previous answer about performance and style.

For ListNode class, I would expect val and next to be named Value and Next. I would also rather see them be properties instead of fields. And for some reason, I am expecting to see a Previous property as well.

I see nothing in the exercise description that says you must create your own implementation of a linked list. Granted, I didn't want to create an account to login to LeetCode.

If the exercise was to create your own linked list, then I would want to see 2 different classes. One would be the ListNode for individual nodes. The other would be a LinkedList, which is a collection of ListNode. Then the method in the HasCycleClass could be moved as a member to LinkedList. As you have it, it feels awkward to have the HasCycleClass where it is.

If the exercise was simply to create an efficient HasCycle method, I would prefer to see you use .NET's LinkedList and LinkedListNode classes.

In summary, I would really prefer to see something about individual nodes as well as a collection of them. Your implementation does not make such a distinction.