Skip to content

Instantly share code, notes, and snippets.

@unilecs
Created October 22, 2017 11:50
Show Gist options
  • Save unilecs/4a7519a22bdac514d838a9ee94e5e0f2 to your computer and use it in GitHub Desktop.
Save unilecs/4a7519a22bdac514d838a9ee94e5e0f2 to your computer and use it in GitHub Desktop.
Найти начало цикла в односвязном списке
using System;
public class Program
{
public class LinkedList
{
public int Value { get; set; }
public LinkedList Next { get; set; }
}
public static LinkedList GetCycleBegin(LinkedList head)
{
LinkedList slowPointer = head;
LinkedList fastPointer = head;
// Находим точку встречи двух указателей
while (fastPointer != null && fastPointer.Next != null)
{
slowPointer = slowPointer.Next;
fastPointer = fastPointer.Next.Next;
if (slowPointer == fastPointer)
{
break;
}
}
// проверка на наличие цикла
if (fastPointer == null || fastPointer.Next == null)
{
return null;
}
// Помещаем медленный указатель в начало списка
// Быстрый указатель оставляем в точке встречи
// запускаем оба указателя с одинаковой скоростью
slowPointer = head;
while (slowPointer != fastPointer)
{
slowPointer = slowPointer.Next;
fastPointer = fastPointer.Next;
}
// если цикл есть, то указатели встретятся в точке начала цикла
return fastPointer;
}
public static void Main()
{
Console.WriteLine("UniLecs");
var root = new LinkedList { Value = 1 };
root.Next = new LinkedList { Value = 2 };
root.Next.Next = new LinkedList { Value = 3 };
root.Next.Next.Next = new LinkedList { Value = 4 };
root.Next.Next.Next.Next = new LinkedList { Value = 5 };
root.Next.Next.Next.Next.Next = root.Next.Next;
Console.WriteLine("Значение точки начала цикла в списке: {0}", GetCycleBegin(root).Value);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment