题目一：判断单链表中是否有环

描述：
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;
}