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

• Gilad: cool! I didn't know that one

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.

• dfhwze: Good point about the question not stating clearly that the Node class is predefined. There are indeed faster algorithms if you were able to change the definition and content of that class.