Поиск цикла в односвязном списке

Найти цикл в односвязном списке и найти узел, с которого начинается цикл.
Я видел использование двух указателей (обычно медленных и быстрых), чтобы найти цикл, но я написал этот код, и он, кажется, работает нормально. У меня вопрос, есть ли что-то, в чем мой код пропускается при поиске цикла в односвязном списке.

Node* find_cycle_node(Node *head){
Node *p=head;
Node *q;
while(p->next!=null)
{
q=p->next;
while(q->next!=null)
{
if(p==q) return q; //Node repeated i.e cycle
else (q=q->next;)
}
p=p->next;
}
return null; // no cycle detected
}

-1

Решение

Ваш внутренний цикл не прекратится, если есть цикл, который представляет собой пару узлов вниз по дескриптору, например, это будет бесконечный цикл для чего-то вроде этого:

1 -> 2 -> 3 -> 4 -> 5
^         |
|         |
+---------+
5

Другие решения

Как насчет этого ?

struct Node_
{
int ix ;
struct Node_* next ;
} ;
typedef struct Node_ NODE ;
NODE *head = NULL ;

int main()
{
NODE* n1 ;
n1 = (NODE*) malloc(sizeof(NODE)) ;
n1->ix = 0 ;
n1->next = NULL ;
head = n1 ;
NODE* n2 ;
n2 = (NODE*) malloc(sizeof(NODE)) ;
n2->ix = 1 ;
n2->next = NULL ;
n1->next = n2 ;
NODE* n3 ;
n3 = (NODE*) malloc(sizeof(NODE)) ;
n3->ix = 2 ;
n3->next = NULL ;
n2->next = n3 ;
NODE* n4 ;
n4 = (NODE*) malloc(sizeof(NODE)) ;
n4->ix = 3 ;
n4->next = n2 ;
n3->next = n4 ;

unordered_map<NODE*,int> hashx ;
int idx ;
NODE* p = head ;
while(p != NULL)
{
hashx[p] += 1 ;
if(hashx[p] >= 2)
{
printf("node p (%d) recycle !!\n",p->ix);
break ;
}
p = p->next ;
}
printf("done \n") ;
} //main
1

есть ли что-то, на чем мой код отсутствует

return; // no cycle detected

Эта строка выглядит довольно плохо, ее следует изменить на s.th. лайк

return NULL; // no cycle detected
0

Для меня состояние вашего внутреннего цикла кажется неоднозначным. Вы анализируете, если (p == q), где q это p-> next. это означает, что ранее рассмотренный узел p не имел ЦИКЛА. Так что для меня твой внутренний цикл никогда не закончится.

Вы должны рассмотреть это: —

#include <iostream>
using namespace std;
class Node{
public:
int data;
Node * next;
Node(int x){
data = x;
next = NULL;
}
Node(int x, Node * y){
data = x;
next = y;
}
};
class linkedList{
Node *head;
public:
linkedList(){
head = NULL;
}
void addNode(int value){
Node *p;
if(head == NULL)
head = new Node (value, NULL);
else{
p = head;
while(p->next !=NULL)
p=p->next;
p->next = new Node (value, NULL);
}
}
void print(){
Node * p;
p = head;
while(p != NULL){
cout << p->data;
p = p->next;
}
}
int findCycle(){
Node *p, *start, *q;
p = head;
while(p != NULL){
q = p->next;
while (q != NULL ){
if(p->data == q->data)
return q->data;
else
q = q->next;
}
p = p->next;
}
return 0;
}
};
int main(){
linkedList l1;
l1.addNode(1);
l1.addNode(2);
l1.addNode(3);
l1.addNode(4);
l1.addNode(5);
l1.addNode(3);
int node = l1.findCycle();
cout<<node;
return 0;
}

Что вы говорите людям об этом коде.

0
void LinkListOps::createCycledListAndFindACycleNode()

{
// построить список с циклом в нем

ZNODE* head = new ZNODE(0);
ZNODE* current = head;
ZNODE* cycle = 0;

for (int i = 1; i < 8; i++)
{
current->_next = new ZNODE(i);
current = current->_next;

if (i == 6)
cycle = current;

if (i == 7)
current->_next = cycle;
}

// verify that there is a cycle
ZNODE* slow = head;
ZNODE* fast = head;
ZNODE* cycleNode = 0;

while (slow && fast && fast->_next)
{
slow = slow->_next;
fast = fast->_next->_next;

if (slow == fast)
{
cycleNode = slow;
break;
}

}

if (cycleNode == 0)
{
printf("No cycle\n");
return;
}

// finally find a cycle node which will be p2
ZNODE* p1 = head;
ZNODE* p2 = cycleNode;

while (1)
{
for (p2 = cycleNode; p2->_next != cycleNode; p2 = p2->_next)
{
if (p2 == p1)
break;
}

if (p2 == p1)
break;

p1 = p1->_next;
}

printf("%d\n", p2->_i);

}

0

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

ptr = head;
current = nullptr;
if (!ptr) {
current = ptr->next;
while(current && current!=ptr) {
current = current->next;
if (current) {
current = current->next;
}
ptr = ptr->next;
}
}

В конце этого, если current не является нулевым, то цикл был найден, и current будет где-то внутри него. Это работает путем итерации current в два раза быстрее по списку, чем ptrи всегда найдет цикл, если таковой существует, до ptr зациклился один раз.

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector