引入

上一节，我们学习了尾指针，并且利用尾指针。尾指针可以轻松的操作头结点和尾结点，可以将两个单循环链表组成了一个单循环链表，我们今天再看看，尾指针还有什么其它玩法。

单链表中的环

首先要明白，单链表有环的状态是什么样子得

其实就是，尾指针指向了链表中的某个结点。

如何判断单链表中是否有环

方法 1

  • 设置 p 、q 两个指针
  • p 向前走，q 从头走，p 向前走尾部应该会到 NULL。
  • 每个结点，p 走的步数应该和 q 一样
  • 如果不一样，就像上面的图，p 的地址等于 q
  • 但是，p 走到3用了6步，q 则用了2步
  • 步数不相等，那么就存在环

方法 2

  • 设置 p 、q 两个指针
  • p 每走一步，q 就走两步，快慢指针
  • 快指针应该很快到 NULL
  • 如果 p==q 了，则存在环

代码实现

#include <stdio.h>
#include <stdlib.h>
#define NUM 10
#define LEN sizeof(struct Link)

struct Link{
    int num;
    struct Link *next;
};

struct Link *create(void){
    struct Link *a,*b,*head;
    a=b=(struct Link *)malloc(LEN);
    int i=0;
    while(i<NUM){
        i++;
        a->num=i;
        if(i==1){
            head=a;
        }else{
            b->next=a;
        }
        b=a;
        a=(struct Link *)malloc(LEN);
    }
    b->next=head->next->next->next->next;  //将尾部指向某个结点
    return head;
}

int hasloop (struct Link *L){
    struct Link *a,*b;
    int step_a=0;
    a=L;
    while(a){
        int step_b=0;
        b=L;
        while(b){
            if(a==b){   //如果地址相同
                if(step_a==step_b){   //如果步数相同，没事
                break;
                }else{    //如果步数不相同，则肯定有指针是通过环过来得
                    printf("第%d个结点存在环\n",step_b+1);
                    return step_b;
                }
            }
            b=b->next;
            step_b++;
        }
        a=a->next;
        step_a++;
    }
    return 0;
}

int main(){
    struct Link *test;
    test=create();
    hasloop(test);
    return 0;
}

代码实现的主要思路就是

  • A 指针走一步
  • B 也走，循环遍历，什么时候走的地址等于 A 走的这一步的地址了
  • 就判断，A 走的这一步的步数等于不等于 B 走的步数
  • 如果地址相等、步数相等，那OK！
  • 如果地址相等，步数不等，那 B 肯定抄近路走环了
  • 就把 b 当前得步数输出出来就行了！，这就是出问题的结点

用快慢指针实现

#include <stdio.h>
#include <stdlib.h>
#define NUM 12
#define LEN sizeof(struct Link)

struct Link{
    int num;
    struct Link *next;
};

struct Link *create(void){
    struct Link *a,*b,*head;
    a=b=(struct Link *)malloc(LEN);
    int i=0;
    while(i<NUM){
        i++;
        a->num=i;
        if(i==1){
            head=a;
        }else{
            b->next=a;
        }
        b=a;
        a=(struct Link *)malloc(LEN);
    }
    b->next=NULL;  //将尾部指向某个结点
    return head;
}
int hasloop (struct Link *L){
    struct Link *normal ,*fast;
    fast=L->next;  //fast 从第2个开始
    normal=L;    //normal 从第1个开始
    while(fast){   //判断 fast 是否为 NULL
        if(fast==normal){    //如果fast地址等于normal的地址
            printf("存在环!\n");
            return 0;
        }else{
            fast=fast->next; //如果地址不同，那么再让 fast 向后移动一位也就是第二位
            if (!fast) {     //判断 fast 是否为 NULL，如果为 NULL，则没有环
                printf("没有环!\n");
            }else{           //否则大家就都向后移动一位
                fast=fast->next;
                normal=normal->next;
            }
        }
    }
    return 0;
}

int main(){
    struct Link *test;
    test=create();
    hasloop(test);
    return 0;
}

用快慢指针的方法大概思路如下

  • 因为normal要移动1位，fast 移动2位
  • 要判断 fast 移动的这两位是否为 NULL 了
  • 如果为 NULL，则一定没有环
  • 如果不为 NULL，那就继续比较
  • 直到地址相同或者遇到 NULL 为止

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。