Найти цикл в односвязном списке и найти узел, с которого начинается цикл.
Я видел использование двух указателей (обычно медленных и быстрых), чтобы найти цикл, но я написал этот код, и он, кажется, работает нормально. У меня вопрос, есть ли что-то, в чем мой код пропускается при поиске цикла в односвязном списке.
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 -> 2 -> 3 -> 4 -> 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
есть ли что-то, на чем мой код отсутствует
return; // no cycle detected
Эта строка выглядит довольно плохо, ее следует изменить на s.th. лайк
return NULL; // no cycle detected
Для меня состояние вашего внутреннего цикла кажется неоднозначным. Вы анализируете, если (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;
}
Что вы говорите людям об этом коде.
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);
}
Вы можете быстро выяснить, есть ли цикл в связанном списке, выполнив следующие действия:
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
зациклился один раз.