Created
October 22, 2017 11:50
-
-
Save unilecs/4a7519a22bdac514d838a9ee94e5e0f2 to your computer and use it in GitHub Desktop.
Найти начало цикла в односвязном списке
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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