题目一：判断单链表中是否有环
描述：
1.有环的定义：链表的尾结点指向了链表中的某个结点
两种解决方案
【方法一】
- 使用
p、q两个指针，p总是向前走，但q每次都从头开始走，对于每个结节点，看p走的步数是否和q一样。如果不一样，就存在环。如图，当p从6走到3时，总共需要6步，此时q从头head出发，只需要两步就到3，步数不等，存在环。
【方法二】利用快慢指针
- 使用
p、q两个指针，p每次向前走一步，q每次向前走两步，若在某个时候，p == q，则存在环。
代码
第一步：创建有环单链表
实际上在前面单链表创建中有两种整表创建的方法(头插法和尾插法)：数据结构学习-线性表之单链表
这里只是最后一个有所改变，让终端结点指向第二个结点,就构成了一个环。
/**
* 随机产生n个元素的值，建立带头结点的单链表L（尾插法）
*/
void CreatListTail(LinkList * L, int n){
LinkList p,r;
int i;
srand(time(0)); /* 初始化随机数种子 */
*L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
r = *L; /* r为指向尾部的结点 */
for (i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Node)); /* 生成新节点 */
p->data = rand()%100 +1; /* 随机生成100以内的数字 */
r->next = p; /* 将表尾终端结点的指针指针指向新节点 */
r = p; /* 将当前的新节点定义为表尾终端结点 */
}
r->next = (*L)->next->next; /* 尾部指向第二个结点(如果无环r->next = null) */
}
第二步：用比较步数的方法【方法一】判断是否有环
用两个while循环实现步数的判断
/**
* 比较步数的方法
*/
int HasLoop(LinkList L){
LinkList cur1 = L; /* 定义结点cur1 */
int pos1 = 0; /* cur1的步数 */
while (cur1) { /* 结点cur1存在 */
LinkList cur2 = L; /* 定义结点cur2 */
int pos2 = 0; /* cur2的步数 */
while (cur2) { /* 结点cur2存在 */
if (cur2 == cur1) { /* 当cur2和cur1到达相同的结点时 */
if (pos1 == pos2) /* cur2和cur1走过的步数一样,说明没有环 */
break;
else{ /* 有环并返回1*/
printf("环的位置在第%d个结点处.\n\n",pos2);
return 1;
}
}
cur2 = cur2->next; /* 若果没有环，继续下一个结点 */
pos2++; /* cur2的步数自增 */
}
cur1 = cur1->next; /* cur1继续向后一个结点 */
pos1++; /* cur1的步数自增 */
}
return 0;
}
第三部：用快慢指针【方法二】
快慢指针在很多地方都有用到，前面一篇单链表练习题中也用过用快慢指针寻找中间节点
/**
* 用快慢指针的方法
*/
int HasLoop2(LinkList L){
LinkList p = L;
LinkList q = L;
while (p != NULL && q != NULL && q->next != NULL) {
p = p->next; /* p每次走一步*/
if (q->next != NULL) {
q = q->next->next; /* p每次走两步*/
}
printf("p:%d, q:%d \n", p->data,q->data);
if (p == q) {
return 1; /* 当p和q相等，则表示有环 */
}
}
return 0;
}
