引入

我们学习了循环链表的基本操作，也学习了一个有趣的约瑟夫问题，我们之前说过有头指针也有尾指针，头指针指向头结点，尾指针指向尾结点。那么尾指针有哪些有趣的用法呢？

单循环链表的问题

我们知道，在单向循环链表中，我们有头指针

  • O ( 1 ) 的时间去找到第一个结点，因为 next 就是头结点
  • O ( n ) 的时间去找最后一个结点，因为第 n 个才是尾结点

如何在访问头结点和尾结点得时候，都是O( 1 )时间复杂度呢？

尾指针应运而生！

  • 尾指针指向的是尾节点
  • 而尾节点得下一个就是头结点

所以尾指针访问头结点和尾节点的时间都是 O ( 1 ) 。
撒花~~~

尾指针

我们看到这张图

  • 尾指针的名称为 rear
  • rear 指向得是终端结点的地址
  • rear 的 next 元素为头结点
  • **特点：**特点就是可以灵活的操作头结点和尾结点

一个例题

创建两个单循环链表，将其合并成一个循环链表。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LEN sizeof(struct Student)
#define NUM 20
struct Student{
    int num;
    struct Student *next;
};

struct Student *create(int min,int max){
    if(min>=max){
        printf("输入错误！");
        return 1;
    }
    struct Student *a,*b,*head;
    int i=min;
    while(min<=max){
        a=(struct Student *)malloc(LEN);
        if(min==i){
            head=a;
        }else{
            b->next=a;
        }
        a->num=min++;
        b=a;
    }
    b->next=head;
    head=b;
    return head;
}

void stu_print(struct Student *stu_p){
    struct Student *head;
    head=stu_p;
    do{
        printf("%d\n",stu_p->next->num);
    }while((stu_p=stu_p->next)!=head);
}

struct Student *stu_mix(struct Student *stu_a,struct Student *stu_b){
    struct Student *mix_a;
    mix_a=stu_a->next;  //保存 a 的头结点位置
    stu_a->next=stu_b->next->next; // A的表尾存储得地址 改为 B头结点存储的位置，A的尾巴连接到B的头。A指向得是头结点指向的
    stu_b->next=mix_a;  // B的表尾存储的地址 改为 A 头结点得地址
    return stu_b;
}

int main(){
    struct Student *stu_a,*stu_b;
    stu_a=create(1,20);
    stu_b=create(21,40);
    stu_print(stu_mix(stu_a,stu_b));
    return 0;
}

合并两个单循环链表有三个步骤

  • 先把 A 的头结点的位置存下来
  • A 的尾巴指向 B 的头结点
  • B 得尾巴指向刚才存下在的 A 的头结点

尾巴

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