Обнаружение цикла в LinkedList с использованием C#

В вопросе интервью: «Реализуйте алгоритм, который обнаруживает наличие цикла». Например, связанный список имеет цикл, например:

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

Используя обнаружение цикла Флойда, эту проблему можно решить с помощью быстрого и медленного указателя. Так что я должен попытаться сравнить

а. Значения узла ссылки, т.е.

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

где быстрое и медленное относятся к типу Link

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

OR

б. Они указывают на одну и ту же ссылку, например if (fast == slow)

Спасибо.


c# linked-list floyd-cycle-finding
person parsh    schedule 02.12.2011    source источник
comment
if (fast == slow) это правильная проверка.   -  person Azodious    schedule 02.12.2011

Ответы (2)


arrow_upward
8
arrow_downward

Вы должны сравнивать только сами узлы. В конце концов, вполне разумно иметь связанный список с повторяющимися данными, фактически не имея цикла.

Я бы тоже назвал их узлами, а не ссылками. Ссылка — это просто ссылка от одного узла к следующему или предыдущему. В частности, нет данных, связанных с ссылкой, только с узлом.

person Jon Skeet    schedule 02.12.2011
comment
Итак, вы говорите, что класс должен был называться так: - Node{ int IData {get; установить;} Узел Далее {получить; установлен;}}. А затем сравнение узлов, например; если (быстро == медленно). Спасибо, на самом деле эта статья заставила меня задуматься о решении: - ссылка - person parsh; 02.12.2011
comment
@parsh: Да, именно так. - person Jon Skeet; 02.12.2011

arrow_upward
0
arrow_downward

Надеюсь, это поможет... Это может быть наивно, но это работает...

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();
    }
   }
 }
person Som    schedule 12.07.2013