c++ - 循环链表的循环起始节点

Question

我正在尝试实现一个程序来查找循环链表的起始节点。我的代码是-

struct node
{
char data;
struct node *link;
} ;

char FindStartNode(struct node **q)
{
    struct node *r,*t;
 r = *q; 
 t = *q;
 while(t->link != NULL)
 {
     r = r->link;
     t = t->link->link;
     if(r == t)
     {
         break;
     }
 }
 if(t == NULL )
     return NULL;
 r = *q;
 while(r != t)
 {
     t = t->link;
     r = r->link;
 }
 return t->data;
}


int main()
{
struct node *p;
p = NULL;
char num;
Append(&p,'A');
Append(&p,'B');
Append(&p,'C');
Append(&p,'D');
Append(&p,'E');
Append(&p,'C');
Display(p);
 num = FindStartNode(&p);
printf("\nStarting node of the cycle linked list is:- %c",num);
_getch();
return 0;
}


int Append(struct node **q, char data)
{
struct node *r,*t;
r = (struct node *)malloc(sizeof(struct node));
r->data = data;
r->link = NULL;
if(*q == NULL)
    *q = r;
else
{
  t = *q;
  while(t->link != NULL)
  {
      t = t->link;
  }
  t->link = r;
    }
return 0;
}
int Display(struct node *q)
{
while(q != NULL)
{
    printf("%c\t",q->data);
    q = q->link;
}
return 0;
}

这是我的代码。我在 return t->data 部分没有得到任何值，或者我无法找到循环墨水列表的起始节点。有什么帮助吗？

Answer 1

 t = t->link->link; // t->link can be null 
   //so t = t->link->link can be a crash or illegal reference

将循环更改为:

 while(t != NULL)
 {
     r = r->link;
     t = t->link;
     if(t == NULL)
       break; // or return no circle
     else t = t->link;
     if(r == t)
     {
         break;
     }
 }

我已经检查了你的代码。对比算法讨论here好像没问题。但是你返回的是 char 为什么不返回一个指针，这样你就可以检查它是否为 NULL。如果它不为空，则发出 pt->tada。这更有意义。

我检查了你的代码，你似乎没有在 Append() 中正确实现循环链​​表。我在下面为您提供了一个有效的实现。看看我是如何修改 Append()

#include <stdio.h>
#include <stdlib.h>

struct node
{
char data;
struct node *link;
} ;

char FindStartNode(struct node **q)
{
    struct node *r,*t;
 r = *q;
 t = *q;
 while(t->link != NULL)
 {
     r = r->link;
     t = t->link->link;
     if(r == t)
     {
         break;
     }
 }
 if(t == NULL )
     return NULL;
 r = *q;
 while(r != t)
 {
     t = t->link;
     r = r->link;
 }
 return t->data;
}

int Append(struct node **q, char data);
int main()
{
struct node *p;
p = NULL;
char num;
Append(&p,'A');
Append(&p,'B');
Append(&p,'C');
Append(&p,'D');
Append(&p,'E');
Append(&p,'C');
//Display(p);
 num = FindStartNode(&p);
printf("\nStarting node of the cycle linked list is:- %c\n",num);
//_getch();
return 0;
}

int Append(struct node **q, char data)
{

struct node *r,*t, *startOfcycle=NULL;
r = (struct node *)malloc(sizeof(struct node));
r->data = data;


r->link = NULL;
if(*q == NULL)
    *q = r;
else
{
  t = *q;
  while(t->link != NULL)
  {
      if(t->data == data)
         startOfcycle = t;

      t = t->link;
  }


  if(startOfcycle == NULL)
  t->link = r;
  else {// there is a cycle point to the start of cycle
     t->link = startOfcycle;
     free(r);
  }
    }
return 0;
}
int Display(struct node *q)
{
while(q != NULL)
{
    printf("%c\t",q->data);
    q = q->link;
}

请注意 Display 函数也是错误的，因为链表的无限循环是循环的。我没有修改它，因为它与你的问题无关。谢谢。