剑指offer之判断链表是否包含环

168 阅读 0 评论 111 点赞

我是靠谱客的博主忧心砖头，最近开发中收集的这篇文章主要介绍剑指offer之判断链表是否包含环，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1 问题

判断链表是否包含环

2 思路

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

3 代码实现

#include <stdio.h>
#include <stdlib.h>
#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 failn");
    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 circlen");
  }
  else
  {
    printf("list do not have circlen");
  }
  return true;
}

4 运行结果