剑指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 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

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

(0)

相关推荐

  • C++实践数组类运算的实现参考

    [项目-数组类运算的实现] 设计数组类Array,为了实现测试函数中要求的功能,请补足相关的函数(构造.析构函数)和运算符重载的函数. 实现策略提示:可以将测试函数中的语句加上注释,取消一句的注释,增加相应的函数,以渐增地实现所有的功能,避免全盘考虑带来的困难. class Array { private: int* list; //用于存放动态分配的数组内存首地址 int size; //数组大小(元素个数) public: //成员函数声明 }; //要求测试函数能够运行出正确.合理的结果:

  • C++实践Time类中的运算符重载参考方法

    [项目-Time类中的运算符重载] 实现Time类中的运算符重载. class CTime { private: unsigned short int hour; // 时 unsigned short int minute; // 分 unsigned short int second; // 秒 public: CTime(int h=0,int m=0,int s=0); void setTime(int h,int m,int s); void display(); //二目的比较运算符

  • 剑指offer之C++语言实现链表(两种删除节点方式)

    1 问题 用C++语言实现链表 2 代码实现 #include <iostream> #include <stdlib.h> using namespace std; class List { public: List(); ~List(); List* createNode(int value);//创建节点 bool insertNode(List *node);//插入节点 void printList();//打印节点 bool deleteNode(List *node)

  • C++项目求Fibonacci数列的参考解答

    [项目:求Fibonacci数列] Fibonacci数列在计算科学.经济学等领域中广泛使用,其特点是:第一.二个数是1,从第3个数开始,每个数是其前两个数之和.据此,这个数列为:1 1 2 3 5 8 13 21 34 55 89 --,请设计程序,输出这个数列,直到这个数字超过10000. [提示]数列可以表示为: [参考解答] #include <iostream> using namespace std; int main( ) { int f1,f2,fn,n; f1=f2=1; n

  • C++实践数组作数据成员的参考

    [项目 - 数组作数据成员]下面是设计好的一个工资类(Salary): class Salary { public: void set_salarys( );//输入职工工资(输入-1标志着工资输入结束),工资保存到salary数组中,实际人数保存到number中: void add_salarys(int x); //给每个人涨x元工资 void sort_salarys(); //对工资由大到小排序 void show_salarys( ); //显示工资信息 private: double

  • 一张图总结C++中关于指针的那些事

    指向对象的指针,指向数据成员的指针,指向成员函数的指针: 数组即指针,数组的指针,指针数组: 指向函数的指针,指向类的成员函数的指针,指针作为函数参数,指针函数: 指针的指针,指向数组的指针:常指针,指向常对象的指针: -- 大哥,这些都是什么鬼?! 用下面一张图全概括.用例子对照图示,有感觉,就用术语将概念大声地念出来,动员所有的感官参与,搞清楚这些,不是事. 图如下: 总结 以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持.如果你想

  • Dijkstra算法最短路径的C++实现与输出路径

    某个源点到其余各顶点的最短路径 这个算法最开始心里怕怕的,不知道为什么,花了好长时间弄懂了,也写了一遍,又遇到时还是出错了,今天再次写它,心里没那么怕了,耐心研究,懂了之后会好开心的,哈哈 Dijkstra算法: 图G 如图:若要求从顶点1到其余各顶点的最短路径,该咋求: 迪杰斯特拉提出"按最短路径长度递增的次序"产生最短路径. 首先,在所有的这些最短路径中,长度最短的这条路径必定只有一条弧,且它的权值是从源点出发的所有弧上权的最小值,例如:在图G中,从源点1出发有3条弧,其中以弧(1

  • C++稀疏矩阵的各种基本运算并实现加法乘法

    代码: #include <iostream> #include<malloc.h> #include<cstdio> using namespace std; #define M 4 #define N 4 #define MaxSize 100 typedef int ElemType; typedef struct { int r; int c; ElemType d;///元素值 } TupNode; ///三元组定义 typedef struct { int

  • C++实践IP地址类项目参考

    [项目-IP地址类] 在互联网中使用的IP地址占4字节,可以用四段法表示,每段值的范围为0-255,中间用"."隔开,例如202.194.116.97.其实,也可以看看一个有4字节的无符号整型值3401741409. 现设计一个IP地址类,用于保存IP地址,并实施在IP地址上的一些操作.如下所示: class IP { private: union //由此匿名联合体可以看出,IP地址共占4个字节 { struct //这是一个由4个字节构成的匿名结构体 { unsigned char

  • C++实践分数类中运算符重载的方法参考

    [项目-分数类中的运算符重载] (1)实现分数类中的运算符重载,在分数类中可以完成分数的加减乘除(运算后再化简).比较(6种关系)的运算. class CFraction { private: int nume; // 分子 int deno; // 分母 public: //构造函数及运算符重载的函数声明 }; //重载函数的实现及用于测试的main()函数 (2)在(1)的基础上,实现分数类中的对象和整型数的四则运算.分数类中的对象可以和整型数进行四则运算,且运算符合交换律.例如:CFrac

随机推荐