如何判断链表是否包含环

今天就跟大家聊聊有关如何判断链表是否包含环,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下内容,希望大家根据这篇文章可以有所收获。

创新互联公司专注于企业成都营销网站建设、网站重做改版、商州网站定制设计、自适应品牌网站建设、成都h5网站建设商城建设、集团公司官网建设、外贸网站制作、高端网站制作、响应式网页设计等建站业务,价格优惠性价比高,为商州等各大城市提供网站开发制作服务。

1 问题

判断链表是否包含环

2 思路

2个指针,一个指针走一步,一个指针走2步,如果相遇则有,反之无。

3 代码实现

#include 
#include 
#define true 1
#define false 0;
typedef struct node
{
  int value;
  struct node *next;
}Node;
/*
 *判断链表是否有环
 */
int isCircleList(Node *head)
{
  if (head == NULL)
  {
    return false;
  }
  Node *first = NULL;
  Node *second = NULL;
  first = head;
  second = head;
  while (second != NULL && (second->next) != NULL && (second->next->next != NULL))
  {
    first = first->next;
    second = second->next->next;
    if (first == second)
    {
      return true;
    }
  }
  return false;
}
int main()
{
  Node *head = NULL;
  Node *node1 = NULL;
  Node *node2 = NULL;
  Node *node3 = NULL;
  Node *node4 = NULL;
  Node *node5 = NULL;
  Node *node6 = NULL;
  Node *node7 = NULL;
  head = (Node *)malloc(sizeof(Node));
  node1 = (Node *)malloc(sizeof(Node));
  node2 = (Node *)malloc(sizeof(Node));
  node3 = (Node *)malloc(sizeof(Node));
  node4 = (Node *)malloc(sizeof(Node));
  node5 = (Node *)malloc(sizeof(Node));
  node6 = (Node *)malloc(sizeof(Node));
  node7 = (Node *)malloc(sizeof(Node));
  if (head == NULL || node1 == NULL || node2 == NULL || node3 == NULL
    || node4 == NULL || node5 == NULL || node6 == NULL || node7 == NULL)
  {
    printf("malloc fail\n");
    return false;
  }
  //       node7<-node6 <-node5
  //       |       |
  //head->node1->node2->node3->node4
  head->value = 0;
  head->next = node1;
  node1->value = 1;
  node1->next = node2;
  node2->value = 2;
  node2->next = node3;
  node3->value = 3;
  node3->next = node4;
  node4->value = 4;
  node4->next = node5;
  node5->value = 5;
  node5->next = node6;
  node6->value = 6;
  node6->next = node7;
  node7->value = 7;
  node7->next = node2;
  int result = isCircleList(head);
  if (result)
  {
    printf("list have circle\n");
  }
  else
  {
    printf("list do not have circle\n");
  }
  return true;
}

4 运行结果

list have circle

看完上述内容,你们对如何判断链表是否包含环有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注创新互联行业资讯频道,感谢大家的支持。


网站名称:如何判断链表是否包含环
分享URL:http://scyanting.com/article/pjsdse.html