劍指offer之判斷鏈表是否包含環

2020-01-26 13:31:19

字體：大中小

來源：轉載

供稿：網友

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 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 運行結果