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

Question

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

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 
} 

Answer 1

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

return; // no cycle detected 

Эта линия выглядит очень плохо, он должен быть изменен на s.th. как

return NULL; // no cycle detected 

Answer 2

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

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

Answer 3

мне ваш условие внутреннего цикла кажется неоднозначным. Вы анализируете if (p == q), где q - p-> next. это означает, что ранее рассмотренный узел p не составлял haD A CYCLE. Таким образом, моя внутренняя петля никогда не прекратится.

вы должны учитывать следующее: -

#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; 
} 

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

Answer 4

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

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 

Answer 5

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); 

}

Answer 6

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

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 не имеет значения NULL, тогда был найден цикл, и current будет где-то внутри него. Это работает путем повторения current в два раза быстрее в списке как ptr и всегда найдет цикл, если он существует, до того, как ptr зациклился один раз.