Как я могу определить, имеет ли одиночный связанный список цикл или нет? Если он имеет цикл, то как найти точку начала цикла, т.е. node, из которой был запущен цикл.
Поиск цикла в односвязном списке
Ответ 1
Вы можете обнаружить это, просто выполнив два указателя по списку, этот процесс известен как алгоритм черепахи и зайца после басни с тем же именем.
Во- первых, проверьте, если список пуст (head является null). Если это так, петля невозможна, поэтому остановитесь сейчас.
В противном случае запустите tortoise первого указателя на head первого узла, а hare второго указателя на head.next второго узла.
Затем продолжайте цикл до тех пор, пока hare станет null (что может быть уже верно в одноэлементном списке), увеличивая tortoise на единицу и hare на два в каждой итерации. Заяц гарантированно достигнет конца первым (если есть конец), так как он стартовал вперед и бежит быстрее.
Если нет конца (то есть, если есть цикл), они в конечном итоге будут указывать на один и тот же узел, и вы можете остановиться, зная, что вы нашли узел где-то внутри цикла.
Рассмотрим следующий цикл, который начинается с 3:
head -> 1 -> 2 -> 3 -> 4 -> 5
^ |
| V
8 <- 7 <- 6
Начиная с tortoise на 1 и hare на 2, они принимают следующие значения:
(tortoise,hare) = (1,2) (2,4) (3,6) (4,8) (5,4) (6,6)
Поскольку они становятся равными в (6,6), и поскольку hare всегда должен быть за tortoise в нецикличном списке, это означает, что вы обнаружили петлю.
Псевдокод будет выглядеть примерно так:
def hasLoop (head):
return false if head = null # Empty list has no loop.
tortoise = head # tortoise initially first element.
hare = tortoise.next # Set hare to second element.
while hare != null: # Go until hare reaches end.
return false if hare.next null # Check enough left for hare move.
hare = hare.next.next # Move hare forward two.
tortoise = tortoise.next # Move tortoise forward one.
return true if hare = tortoise # Same means loop found.
endwhile
return false # Loop exit means no loop.
enddef
Временная сложность для этого алгоритма составляет O(n) так как количество посещенных узлов (черепахой и зайцем) пропорционально количеству узлов.
Как только вы знаете узел в цикле, также существует гарантированный метод O(n) чтобы найти начало цикла.
Вернемся к исходной позиции после того, как вы нашли элемент где-то в цикле, но вы не уверены, где находится начало цикла.
head -> 1 -> 2 -> 3 -> 4 -> 5
^ |
| V
8 <- 7 <- 6
\
x (where hare and tortoise met).
Это процесс для подражания:
- Заранее
hareи установитеsize1. - Затем, если
hareиtortoiseразные, продолжайте продвигатьhare, увеличиваяsizeкаждый раз. Это в конечном итоге дает размер цикла, шесть в данном случае. - На этом этапе, если
sizeравен1, это означает, чтоyou must *already* be at the start of the loop (in a loop of size one, there is only one possible node that can *be* in the loop so it *must* be the first in that loop). In this case, you simply returnyou must *already* be at the start of the loop (in a loop of size one, there is only one possible node that can *be* in the loop so it *must* be the first in that loop). In this case, you simply returnhare 'в качестве начала и пропускаете остальные шаги ниже. - В противном случае установите для
hareиtortoiseпервый элемент списка иharesizehare(в данном случае до7). Это дает два указателя, которые отличаются точно размером цикла. - Затем, если
hareиtortoiseотличаются друг от друга, продвигайте их обоих вместе (при том, что заяц бежит в более спокойном темпе, с той же скоростью, что и черепаха - я думаю, он устал от первого запуска). Так как они всегда будут точно соответствоватьsizeэлементов друг от друга,tortoiseдостигнет начала цикла ровно в то же время, когдаhareвернутся к началу цикла.
Вы можете увидеть это с помощью следующего пошагового руководства:
size tortoise hare comment
---- -------- ---- -------
6 1 1 initial state
7 advance hare by six
2 8 1/7 different, so advance both together
3 3 2/8 different, so advance both together
3/3 same, so exit loop
Следовательно, 3 является начальной точкой цикла, и, поскольку обе эти операции (обнаружение цикла и обнаружение начала цикла) выполняются O(n) и выполняются последовательно, все вместе взятые также составляет O(n).
Если вы хотите более формальное доказательство того, что это работает, вы можете изучить следующие ресурсы:
- вопрос на нашем родственном сайте;
- страница обнаружения цикла Википедии; или же
- "Черепаха и алгоритм зайца", Питер Гэмми, 17 апреля 2016 г.
Если вы просто поддерживаете метод (не формальное доказательство), вы можете запустить следующую программу на Python 3, которая оценивает его работоспособность для большого количества размеров (сколько элементов в цикле) и вводных элементов (элементов перед начало цикла).
Вы найдете, что он всегда находит точку, где встречаются два указателя:
def nextp(p, ld, sz):
if p == ld + sz:
return ld
return p + 1
for size in range(1,1001):
for lead in range(1001):
p1 = 0
p2 = 0
while True:
p1 = nextp(p1, lead, size)
p2 = nextp(nextp(p2, lead, size), lead, size)
if p1 == p2:
print("sz = %d, ld = %d, found = %d" % (size, lead, p1))
break
Ответ 2
Выбранный ответ дает решение O (n * n) для поиска начала цикла node. Здесь O (n) решение:
Как только мы обнаружим, что медленное A и быстрое B встречаются в цикле, сделайте один из них неподвижным, а другой продолжайте идти один шаг каждый раз, чтобы определить периметр цикла, скажем, P.
Затем мы помещаем a node в голову и позволяем ему идти на шаги P и кладем еще один node по голове. Мы продвигаем эти два узла как один шаг каждый раз, когда они впервые встречаются, это начальная точка цикла.
Ответ 3
Вы можете использовать хэш-карту также для определения того, имеет ли список ссылок цикл или не ниже. Функция использует хэш-карту, чтобы выяснить, имеет ли список ссылок цикл или нет.
static bool isListHaveALoopUsingHashMap(Link *headLink) {
map<Link*, int> tempMap;
Link * temp;
temp = headLink;
while (temp->next != NULL) {
if (tempMap.find(temp) == tempMap.end()) {
tempMap[temp] = 1;
} else {
return 0;
}
temp = temp->next;
}
return 1;
}
Метод с двумя указателями - лучший подход, поскольку временная сложность - это O (n). Карта хэша требует добавления O (n) сложности пространства.
Ответ 4
Я прочитал этот ответ в книге структуры данных Нарасимхи Караманчи.
Мы можем использовать алгоритм поиска циклов Floyd, также известный как алгоритм черепахи и зайца. В этом случае используются два указателя; один (скажем, slowPtr) продвигается одним node, а другой (скажем, fastPtr) продвигается двумя узлами. Если какой-либо цикл присутствует в единственном связанном списке, они оба наверняка встречаются в какой-то момент.
struct Node{
int data;
struct Node *next;
}
// program to find the begin of the loop
int detectLoopandFindBegin(struct Node *head){
struct Node *slowPtr = head, *fastPtr = head;
int loopExists = 0;
// this while loop will find if there exists a loop or not.
while(slowPtr && fastPtr && fastPtr->next){
slowPtr = slowPtr->next;
fastPtr = fastPtr->next->next;
if(slowPtr == fastPtr)
loopExists = 1;
break;
}
Если существует какая-либо петля, то мы указываем один из указателей на голову и теперь продвигаем оба из них одним node. node, в котором они будут встречаться, будет началом node цикла в единственном связанном списке.
if(loopExists){
slowPtr = head;
while(slowPtr != fastPtr){
fastPtr = fastPtr->next;
slowPtr = slowPtr->next;
}
return slowPtr;
}
return NULL;
}
Ответ 5
По большей части все предыдущие ответы верны, но здесь представлена упрощенная версия логики с визуальным и программным кодом (для Python 3.7)
Логика очень проста, как объяснили другие. Я собираюсь создать Черепаху/медленно и Заяц/быстро. Если мы переместим два указателя с разной скоростью, то в конце концов быстрый будет соответствовать медленному !! Вы также можете думать об этом как о двух бегунах в круговом поле. Если быстрый бегун продолжает движение по кругу, он встречает/проходит медленного бегуна.
Таким образом, мы будем перемещать указатель "Черепаха/медленный" со скоростью 1 для каждой итерации, в то время как мы продолжаем увеличивать или перемещать указатель "Зайчик/быстрый" со скоростью 2. Как только они встретятся, мы знаем, что есть цикл. Это также известно как алгоритм обнаружения цикла Флойда 
Вот код Python, который делает это (обратите внимание, что метод has_cycle является основной частью):
#!/usr/bin/env python3
class Node:
def __init__(self, data = None):
self.data = data
self.next = None
def strnode (self):
print(self.data)
class LinkedList:
def __init__(self):
self.numnodes = 0
self.head = None
def insertLast(self, data):
newnode = Node(data)
newnode.next = None
if self.head == None:
self.head = newnode
return
lnode = self.head
while lnode.next != None :
lnode = lnode.next
lnode.next = newnode # new node is now the last node
self.numnodes += 1
def has_cycle(self):
slow, fast = self.head ,self.head
while fast != None:
if fast.next != None:
fast = fast.next.next
else:
return False
slow = slow.next
if slow == fast:
print("--slow",slow.data, "fast",fast.data)
return True
return False
linkedList = LinkedList()
linkedList.insertLast("1")
linkedList.insertLast("2")
linkedList.insertLast("3")
# Create a loop for testing
linkedList.head.next.next.next = linkedList.head;
#let check and see !
print(linkedList.has_cycle())
Ответ 6
Следующий код найдет, есть ли цикл в SLL, и если он вернется, то начнется node.
int find_loop(Node *head){
Node * slow = head;
Node * fast = head;
Node * ptr1;
Node * ptr2;
int k =1, loop_found =0, i;
if(!head) return -1;
while(slow && fast && fast->next){
slow = slow->next;
/*Moving fast pointer two steps at a time */
fast = fast->next->next;
if(slow == fast){
loop_found = 1;
break;
}
}
if(loop_found){
/* We have detected a loop */
/*Let count the number of nodes in this loop node */
ptr1 = fast;
while(ptr1 && ptr1->next != slow){
ptr1 = ptr1->next;
k++;
}
/* Now move the other pointer by K nodes */
ptr2 = head;
ptr1 = head;
for(i=0; i<k; i++){
ptr2 = ptr2->next;
}
/* Now if we move ptr1 and ptr2 with same speed they will meet at start of loop */
while(ptr1 != ptr2){
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return ptr1->data;
}
Ответ 7
boolean hasLoop(Node *head)
{
Node *current = head;
Node *check = null;
int firstPtr = 0;
int secondPtr = 2;
do {
if (check == current) return true;
if (firstPtr >= secondPtr){
check = current;
firstPtr = 0;
secondPtr= 2*secondPtr;
}
firstPtr ++;
} while (current = current->next());
return false;
}
Другое решение O (n).
Ответ 8
Когда я просмотрел выбранный ответ, я попробовал пару примеров и обнаружил, что:
Если (A1, B1), (A2, B2)... (AN, BN) - обход указателей A и B
где A шагов 1 и B шагов 2, а Ai и Bj - узлы, пересекаемые A и B, и AN = BN.
Затем node, из которого начинается цикл, является Ak, где k = пол (N/2).
Ответ 9
ok - Я столкнулся с этим в интервью вчера - никаких доступных справочных материалов, и я придумал совершенно другой ответ (во время поездки домой, конечно...) Поскольку связанные списки являются НОРМАЛЬНЫМИ (не всегда я допускаю) используя логику malloc, мы знаем, что гранулярность распределений известна. В большинстве систем это 8 байтов - это означает, что нижние 3 бита всегда нули. Подумайте - если мы поместим связанный список в класс для управления доступом и используем маску 0x0E, или добавили в следующий адрес, тогда мы можем использовать более низкие 3 бита для хранения разрывной крошки. Таким образом, мы можем написать метод, который будет хранить наш последний пакет - скажем 1 или 2 - и чередовать их. Наш метод, который проверяет цикл, может затем пройти через каждый node (используя наш следующий метод) и проверить, содержит ли следующий адрес текущую палитру - если у нас есть цикл - если это не так, мы будем маскировать нижний 3 бита и добавьте нашу текущую панировку. Алгоритм проверки пакетирования должен быть однопоточным, так как вы не могли запустить сразу два из них, но это позволило бы другим потокам получить доступ к списку async - с обычными оговорками о добавлении/удалении узлов. Как вы думаете? Если другие считают, что это правильное решение, я могу написать образец класса... Просто подумайте, что свежий подход хорош, и я всегда готов сказать, что я просто пропустил точку... Спасибо всем Mark
Ответ 10
Другое решение
Обнаружение циклы:
- создать список
- переберите связанный список и продолжайте добавлять узел в список.
- Если узел уже присутствует в списке, у нас есть цикл.
Удаление циклы:
- На шаге № 2, приведенном выше, пока мы перебираем связанный список, мы также отслеживаем предыдущий узел.
-
Как только мы обнаружим цикл в Шаге № 3, установите следующее значение предыдущего узла равным NULL
#код
def detect_remove_loop (head)
cur_node = head node_list = [] while cur_node.next is not None: prev_node = cur_node cur_node = cur_node.next if cur_node not in node_list: node_list.append(cur_node) else: print('Loop Detected') prev_node.next = None return print('No Loop detected')
Ответ 11
Во-первых, создайте узел
struct Node {
int data;
struct Node* next;
};
Инициализировать указатель головы глобально
Struct Node* head = NULL;
Вставьте некоторые данные в связанный список
void insert(int newdata){
Node* newNode = new Node();
newNode->data = newdata;
newNode->next = head;
head = newNode;
}
Создать функцию detectLoop()
void detectLoop(){
if (head == NULL || head->next == NULL){
cout<< "\nNo Lopp Found in Linked List";
}
else{
Node* slow = head;
Node* fast = head->next;
while((fast && fast->next) && fast != NULL){
if(fast == slow){
cout<<"Loop Found";
break;
}
fast = fast->next->next;
slow = slow->next;
}
if(fast->next == NULL){
cout<<"Not Found";
}
}
}
Вызов функции из main()
int main()
{
insert(4);
insert(3);
insert(2);
insert(1);
//Created a Loop for Testing, Comment the next line to check the unloop linkedlist
head->next->next->next->next = head->next;
detectLoop();
//If you uncomment the display function and make a loop in linked list and then run the code you will find infinite loop
//display();
}
Ответ 12
Совсем другой метод: Переверните связанный список. Если вы вернетесь в голову снова, тогда в списке есть петля, если вы получите NULL, тогда нет цикла. Общая временная сложность O (n)