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.