循环链表

将单链表中终端结点的指针段由空指针改为指向头结点，就使整个单链表形成了一个环，这种头尾相连的单链表简称循环链表。

这样循环链表就解决了一个问题:如何从一个结点出发，访问到链表的全部结点。

为了使空链表和非空链表处理一致，我们通常设一个头结点，当然，并不是说循环链表一定要有头结点。

其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是判断其不等于头结点，则循环未结束。

循环链表的定义

与普通的单链表并无二致，只是将尾指针链接到头结点上，而非之前的NULL，而指针域我们存的不再是头指针，而是尾指针。

typedef struct LNode {    ElemType data; //数据域    struct LNode *next; //指针域,存的不再是头指针，而是尾指针}LNode, *LinkList;

循环链表的初始化

尾插法，每次都要让尾指针指向头结点，最后入我们让链表的头结点里面存的是尾指针即可。

void InitList(LinkList &L, int n){    L = (LNode*)malloc(sizeof(LNode));    if(!L) exit(0);    L->next = L; //初始化头结点，尾指针指向头结点    LNode *p, *tail = L;    for(int i = 1; i <= n; ++i) {        p = (LNode*)malloc(sizeof(LNode));        if(!p) exit(0);        p->data = i;        tail->next = p;        p->next = L;        tail = p;    }    L = p; //将尾指针赋值给指针域}

---

循环链表的合并

由于我们存储了尾指针，所以合并两个链表变得非常的简单,下面我们将A链表连接到B链表上。

void ConnectList(LinkList &rearA, LinkList &rearB) //将A链表连接到B链表上{    LNode *p, *q;    p = rearA->next;   //保存A的头结点    rearA->next = rearB->next->next; //将本是指向B的第一个结点(不是头结点),赋值给rearA->next    q = rearB->next;     rearB->next = p;  //将原A表的头结点赋值给rearB->next    free(q);  //释放q}

循环链表的遍历

因为我们的头结点里面存储的是尾指针，所以我们需要使用L->next->next来得到第一个结点的位置。

void traverse(LinkList L){    LNode *p = L->next->next;    while(p != L->next) {        printf("%d ", p->data);        p = p->next;    }    puts("");}