结构之美：判断单链表中是否有环

转自：结构之美：判断单链表中是否有环


有环的定义是，链表的尾节点指向了链接中间的某个节点。比如下图，如果单链表有环，则在遍历时，在通过6之后，会重新回到3，那么我们可以在遍历时使用两个指针，看两个指针是否相等。
方法一：使用p、q两个指针，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样。如图，当p从6走到3时，用了6步，此时若q从head出发，则只需两步就到3，因而步数不等，出现矛盾，存在环。
方法二：使用p、q两个指针，p每次向前走一步，q每次向前走两步，若在某个时候p == q，则存在环。
对于方法一，其实现代码为：

01//if two pointer are equal, but they don't have the same steps, then has a loop
02int HasLoop(LinkList L)
03{
04    LinkList cur1 = L;  // 定义结点 cur1
05    int pos1 = 0;       // cur1 的步数
06    while(cur1){        // cur1 结点存在
07        LinkList cur2 = L;  // 定义结点 cur2
08        int pos2 = 0;       // cur2 的步数
09        pos1 ++;            // cur1 步数自增
10        while(cur2){        // cur2 结点不为空
11            pos2 ++;        // cur2 步数自增
12            if(cur2 == cur1){   // 当cur1与cur2到达相同结点时
13                if(pos1 == pos2)    // 走过的步数一样
14                    break;          // 说明没有还
15                else                // 否则
16                    return 1;       // 有环并返回1
17            }
18            cur2 = cur2->next;      //  如果没发现环，继续下一个结点
19        }
20        cur1 = cur1->next;  // cur1继续向后一个结点
21    }
22    return 0;
23}

方法二则比较简单，就不注释了。

01//using step1 and step2 here
02//if exists a loop, then the pointer which use step2 will catch up with the pointer which uses step1
03int HasLoop2(LinkList L)
04{
05    int step1 = 1;
06    int step2 = 2;
07    LinkList p = L;
08    LinkList q = L;
09    //while (p != NULL && q != NULL && q->next == NULL)
10    while (p != NULL && q != NULL && q->next != NULL)
11    {
12        p = p->next;
13        if (q->next != NULL)
14            q = q->next->next;
15        printf("p:%d, q:%d \n", p->data, q->data);
16        if (p == q)
17            return 1;
18    }
19    return 0;
20}

完整的可执行程序如下：

001#include "stdio.h"
002
003#define OK 1
004#define ERROR 0
005#define TRUE 1
006#define FALSE 0
007
008typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
009typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
010
011typedef struct Node
012{
013    ElemType data;
014    struct Node *next;
015}Node;
016typedef struct Node *LinkList; /* 定义LinkList */
017
018Status visit(ElemType c)
019{
020    printf("%d ",c);
021    return OK;
022}
023
024/* 初始化顺序线性表 */
025Status InitList(LinkList *L)
026{
027    *L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
028    if(!(*L)) /* 存储分配失败 */
029            return ERROR;
030    (*L)->next=NULL; /* 指针域为空 */
031
032    return OK;
033}
034
035/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
036int ListLength(LinkList L)
037{
038    int i=0;
039    LinkList p=L->next; /* p指向第一个结点 */
040    while(p)
041    {
042        i++;
043        p=p->next;
044    }
045    return i;
046}
047
048/* 初始条件：顺序线性表L已存在 */
049/* 操作结果：依次对L的每个数据元素输出 */
050Status ListTraverse(LinkList L)
051{
052    LinkList p=L->next;
053    while(p)
054    {
055        visit(p->data);
056        p=p->next;
057    }
058    printf("\n");
059    return OK;
060}
061
062/*  随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
063void CreateListHead(LinkList *L, int n)
064{
065    LinkList p;
066    int i;
067    srand(time(0));                         /* 初始化随机数种子 */
068    *L = (LinkList)malloc(sizeof(Node));
069    (*L)->next = NULL;                      /*  先建立一个带头结点的单链表 */
070    for (i=0; i < n; i++)
071    {
072        p = (LinkList)malloc(sizeof(Node)); /*  生成新结点 */
073        p->data = rand()%100+1;             /*  随机生成100以内的数字 */
074        p->next = (*L)->next;
075        (*L)->next = p;                      /*  插入到表头 */
076    }
077}
078
079/*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
080void CreateListTail(LinkList *L, int n)
081{
082    LinkList p,r;
083    int i;
084    srand(time(0));                      /* 初始化随机数种子 */
085    *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
086    r=*L;                                /* r为指向尾部的结点 */
087    for (i=0; i < n; i++)
088    {
089        p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
090        p->data = rand()%100+1;           /*  随机生成100以内的数字 */
091        r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
092        r = p;                            /* 将当前的新结点定义为表尾终端结点 */
093    }
094    r->next = NULL;                       /* 表示当前链表结束 */
095    // 创建有环链表
096    //r->next = p;
097}
098
099/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
100/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
101Status ListDelete(LinkList *L,int i,ElemType *e)
102{
103    int j;
104    LinkList p,q;
105    p = *L;
106    j = 1;
107    while (p->next && j < i)  /* 遍历寻找第i个元素 */
108    {
109        p = p->next;
110        ++j;
111    }
112    if (!(p->next) || j > i)
113        return ERROR;           /* 第i个元素不存在 */
114    q = p->next;
115    p->next = q->next;            /* 将q的后继赋值给p的后继 */
116    *e = q->data;               /* 将q结点中的数据给e */
117    free(q);                    /* 让系统回收此结点，释放内存 */
118    return OK;
119}
120
121int HasLoop(LinkList L)
122{
123    LinkList cur1 = L;  // 定义结点 cur1
124    int pos1 = 0;       // cur1 的步数
125    while(cur1){        // cur1 结点存在
126        LinkList cur2 = L;  // 定义结点 cur2
127        int pos2 = 0;       // cur2 的步数
128        pos1 ++;            // cur1 步数自增
129        while(cur2){        // cur2 结点不为空
130            pos2 ++;        // cur2 步数自增
131            if(cur2 == cur1){   // 当cur1与cur2到达相同结点时
132                if(pos1 == pos2)    // 走过的步数一样
133                    break;          // 说明没有还
134                else                // 否则
135                    return 1;       // 有环并返回1
136            }
137            cur2 = cur2->next;      //  如果没发现环，继续下一个结点
138        }
139        cur1 = cur1->next;  // cur1继续向后一个结点
140    }
141    return 0;
142}
143
144//using step1 and step2 here
145//if exists a loop, then the pointer which use step2 will catch up with the pointer which uses step1
146int HasLoop2(LinkList L)
147{
148    int step1 = 1;
149    int step2 = 2;
150    LinkList p = L;
151    LinkList q = L;
152    //while (p != NULL && q != NULL && q->next == NULL)
153    while (p != NULL && q != NULL && q->next != NULL)
154    {
155        p = p->next;
156        if (q->next != NULL)
157            q = q->next->next;
158        printf("p:%d, q:%d \n", p->data, q->data);
159        if (p == q)
160            return 1;
161    }
162    return 0;
163}
164
165int main()
166{
167    LinkList L;
168    Status i;
169    char opp;
170    ElemType e;
171    int find;
172    int tmp;
173
174    i=InitList(&L);
175    printf("初始化L后：ListLength(L)=%d\n",ListLength(L));
176
177    printf("\n1.查看链表 \n2.创建链表（尾插法） \n3.链表长度 \n4.判断链表是否有环 \n0.退出 \n请选择你的操作：\n");
178    while(opp != '0'){
179        scanf("%c",&opp);
180        switch(opp){
181            case '1':
182                ListTraverse(L);
183                printf("\n");
184                break;
185
186            case '2':
187                CreateListTail(&L,20);
188                printf("整体创建L的元素(尾插法)：\n");
189                ListTraverse(L);
190                printf("\n");
191                break;
192
193            case '3':
194                //clearList(pHead);   //清空链表
195                printf("ListLength(L)=%d \n",ListLength(L));
196                printf("\n");
197                break;
198
199            case '4':
200                //find = HasLoop(L);
201                if( HasLoop(L) )
202                {
203                    printf("方法一: 链表有环\n");
204                }
205                else
206                {
207                    printf("方法一: 链表无环\n");
208                }
209
210                if( HasLoop2(L) )
211                {
212                    printf("方法二: 链表有环\n");
213                }
214                else
215                {
216                    printf("方法二: 链表无环\n");
217                }
218                ListTraverse(L);
219                printf("\n");
220                break;
221
222            case '0':
223                exit(0);
224        }
225    }
226
227}

延伸阅读

此文章所在专题列表如下：
  1. 结构之美：定义一个线性表
  2. 结构之美：线性表的查找、插入与删除操作
  3. 结构之美：线性表的链式存储结构——链表
  4. 结构之美：单链表的初始化、创建与遍历
  5. 结构之美：单链表的头结点与头指针
  6. 结构之美：使用头插法创建单链表
  7. 结构之美：使用尾插法创建单链表
  8. 结构之美：单链表的销毁删除
  9. 结构之美：查找单链表指定位置结点的数据
  10. 结构之美：在单链表指定位置插入数据
  11. 结构之美：删除单链表指定位置的数据
  12. 结构之美：单链表逆序
  13. 结构之美：判断单链表中是否有环
  14. 结构之美：获取单链表倒数第N个结点值
  15. 单循环链表的初始化、创建、删除、查找与遍历
  16. 结构之美：双向循环链表的结构与定义

本文地址：http://www.nowamagic.net/librarys/veda/detail/1837，欢迎访问原出处。




时间：