Loop detection in LinkedList using C#

Question

In the interview question, "Implement an algorithm which detects for presence of the loop.". For example, the linked list has a loop, like:

0--->1---->2---->3---->4---->5---->6
                 ▲                 |
                 |                 ▼
                11<—-22<—-12<—-9<—-8

Using Floyd's cycle detection, this problem can be solved by using a fast & slow pointer. So should I try comparing

a. Link's node values, i.e.

if (fast.data == slow.data) 
    break;

where fast and slow are of type Link

class Link
{
    int IData {get; set;}
    Link Next {get; set;}
}

OR

b. Are they pointing to same reference, i.e. if (fast == slow)

Thanks.

if (fast == slow) is correct check.

Azodious
– Azodious

2011-12-02 07:17:01 +00:00
Commented Dec 2, 2011 at 7:17 — Azodious
– Azodious, Commented Dec 2, 2011 at 7:17

Jon Skeet · Accepted Answer · 2011-12-02 07:13:42Z

8

You should only be comparing the nodes themselves. After all, it's reasonable to have a linked list with repeated data in, without it actually having a cycle.

I would call them nodes rather than links too. A link is simply the reference from one node to the next or previous one - in particular, there's no data associated with a link, only with a node.

answered Dec 2, 2011 at 7:13

Jon Skeet

1.5m893 gold badges9.3k silver badges9.3k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

parsh Over a year ago

So what you are saying is the class should have been named like:- Node{ int IData {get; set;} Node Next {get; set;}}. And then comparing nodes like; if (fast == slow). Thanks, actually this article kinda got me thinking about the solution:- link

Jon Skeet Over a year ago

@parsh: Yes, that's exactly it.

Som · Accepted Answer · 2013-07-12 20:03:57Z

Hope this helps... It might be naive but it works...

using System;

namespace CSharpTestTemplates
{
class LinkedList
{
    Node Head;

    public class Node
    {
        public int value;
        public Node NextNode;

        public Node(int value)
        {
            this.value = value;
        }
    }

    public LinkedList(Node head)
    {
        this.Head = head;
    }



    public Boolean hasLoop()
    {
        Node tempNode = Head;
        Node tempNode1 = Head.NextNode;
        while(tempNode!=null && tempNode1!=null){
            if(tempNode.Equals(tempNode1)){
                return true;
            }

            if ((tempNode1.NextNode != null) && (tempNode.NextNode != null))
            {
                tempNode1 = tempNode1.NextNode.NextNode;
                tempNode = tempNode.NextNode;
            }
            else
            {
                return false;
            }
        }

        return false;
    }

    public static void Main()
    {
        Node head = new Node(1);
        LinkedList ll = new LinkedList(head);

        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);

        head.NextNode = node2;
        node2.NextNode = node3;
        node3.NextNode = node4;
        node4.NextNode = node5;
        node5.NextNode = node6;
        node6.NextNode = null;

        Console.WriteLine(ll.hasLoop());
        Console.Read();
    }
   }
 }

Collectives™ on Stack Overflow

Loop detection in LinkedList using C#

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related