Поиск цикла в односвязном списке
Как я могу определить, имеет ли одиночный связанный список цикл или нет?
Если он имеет цикл, то как найти точку начала цикла, т.е. 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
и установите size
1
. - Затем, если
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 return
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 return
hare 'в качестве начала и пропускаете остальные шаги ниже. - В противном случае установите для
hare
и tortoise
первый элемент списка и hare
size
hare
(в данном случае до 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)
.
Если вы хотите более формальное доказательство того, что это работает, вы можете изучить следующие ресурсы:
Если вы просто поддерживаете метод (не формальное доказательство), вы можете запустить следующую программу на 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. Как только они встретятся, мы знаем, что есть цикл. Это также известно как алгоритм обнаружения цикла Флойда ![enter image description here]()
Вот код 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)