单循环链表

单循环链表：将单链表中终端结点的next域由空指针改为指向头结点，就使得整个单链表形成一个环，这种头尾相接的单链表称为单循环链表。
如下图所示

单循环链表
1.循环链表和单链表的主要差异在于循环的判断条件上，原来是判断p->next是否为空，现在则是p->next是否为头结点
2.选择不用头指针，而是用指向终端结点的尾指针rear来表示循环链表，则查找开始结点和终端结点都很方便快捷

LinkList_cycle.h

#pragma once

// 函数结果状态代码
#define OK      1
#define ERROR   0
#define INFEASIBLE  -1
#define OVERFLOW    -2

//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;

//数据类型
typedef int ElemType;

typedef struct LNode
{
    ElemType data;
    LNode* next;

}LNode, * LinkList_cycle;

//初始化链表
Status InitList_cycle(LinkList_cycle& L);

//判空
bool ListEmpty_cycle(LinkList_cycle L);

//销毁单链表（包括头结点在内的所有结点）
Status DestroyList_cycle(LinkList_cycle& L);

//遍历单循环链表
void ListTraverse_cycle(LinkList_cycle L);

//头插法建立单循环链表（返回尾指针）
LinkList_cycle CreateList_cycle_H(LinkList_cycle& L_H, int n);

//尾插法建立单循环链表（返回尾指针）
LinkList_cycle CreateList_cycle_T(LinkList_cycle& L_T, int  n);

//合并两个用尾指针表示的单循环链表,合并后将另一个销毁
void Connect(LinkList_cycle& rear_H, LinkList_cycle& rear_T);

LinkList_cycle.cpp

#include "LinkList_cycle.h"
#include <iostream>
using namespace std;

//初始化链表
Status InitList_cycle(LinkList_cycle& L)
{
    L = new LNode;
    L->next = L;    //与单链表不同的是其头结点的next域指向头结点，而单链表的情况是指向NULL

    cout << "初始化循环链表成功" << endl;
    return OK;
}

//判空
bool ListEmpty_cycle(LinkList_cycle L)
{
    if (L)                  //头结点存在
    {
        if (L->next == L)   //第一个结点不存在
        {
            cout << "循环链表为空" << endl;
            return true;
        }
        else
        {
            cout << "循环链表不为空" << endl;
            return false;
        }
    }
    else
    {
        cout << "循环链表不存在" << endl;
        return true;
    }
}

//销毁单循环链表（包括头结点在内的所有结点）
//需要根据头结点判断循环结束条件，先删除除头结点之外的所有结点，再删除头结点
Status DestroyList_cycle(LinkList_cycle& L)
{

    LNode* p = L->next;                 //第一个结点
    LNode* q;
    while (p != L)              //结束条件为p=头结点
    {
        q = p->next;
        delete p;
        p = q;
    }
    delete L;
    cout << "销毁成功" << endl;
    return OK;
}

//遍历单循环链表
void ListTraverse_cycle(LinkList_cycle L)
{
    LNode* p = L->next;
    while (p != L)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

//头插法建立单循环链表,并返回此链表的尾指针
LinkList_cycle CreateList_cycle_H(LinkList_cycle& L_H, int n)
{
    L_H = new LNode;
    L_H->next = L_H;                //单循环链表空表

    LNode* rear = L_H;              //开始时尾指针指向头结点
    for (int i = n; i > 0; i--)
    {
        LNode* p = new LNode;       //建立新结点
        p->data = i;
        p->next = L_H->next;        //新结点的next域指向原来头结点的next域指向的结点
        L_H->next = p;              //头结点的next域指向新结点
        if (p->next == L_H)         //如果p的next域指向的结点为头结点
        {
            rear = p;               //更新尾指针
        }
    }
    return rear;
}

//尾插法建立单循环链表（返回尾指针）
LinkList_cycle CreateList_cycle_T(LinkList_cycle& L_T, int  n)
{
    L_T = new LNode;
    L_T->next = L_T;                //单循环链表的空表

    LNode* rear = L_T;              //记录尾指针，开始就为头结点
    for (int i = 1; i <= n; i++)
    {
        LNode* p = new LNode;       //建立新结点
        p->data = i + 5;
        p->next = rear->next;       //新结点指向头结点，即尾指针的next域指向的结点
        rear->next = p;             //原来尾指针指向的next域为新结点
        rear = p;                   //尾指针更新为指向新结点
    }
    return rear;
}

两个单循环链表合并：

合并

1.保存第一个链表的头结点
2.第一个链表尾指针的next域指向第二个链表的第一个结点
3.第二个链表的尾指针的next域指向第一个链表的头结点

//合并两个用尾指针表示的单循环链表到第一个链表中
void Connect(LinkList_cycle& rear_H, LinkList_cycle& rear_T)
{
    LinkList_cycle L_H = rear_H->next;      //第一个链表的头结点
    rear_H->next = rear_T->next->next;      //第一个链表的尾指针的next域指向第二个链表的第一个结点
    rear_T->next = L_H;                     //第二个链表的尾指针指向第一个链表的头结点

    cout << "合并成功" << endl;
}

main.cpp

测试：

#include "LinkList_cycle.h"

#include <iostream>
using namespace std;

int main(int argc, char** argv)
{
    LinkList_cycle L;

    InitList_cycle(L);                  //初始化单循环链表
    ListEmpty_cycle(L);                 //判空
    DestroyList_cycle(L);               //销毁

    LinkList_cycle L_H;
    LNode* rear_H = CreateList_cycle_H(L_H, 5);     //头插法创建
    ListTraverse_cycle(L_H);                        //遍历
    cout << "单循环链表第一个结点:" << rear_H->next->next->data << endl;

    LinkList_cycle L_T;
    LNode* rear_T = CreateList_cycle_T(L_T, 5);     //尾插法创建
    ListTraverse_cycle(L_T);                        //遍历
    cout << "单循环链表第一个结点:" << rear_T->next->next->data << endl;

    Connect(rear_H, rear_T);                        //合并两个链表到rear_H中
    ListTraverse_cycle(rear_T->next);               //遍历合并后的链表
    ListTraverse_cycle(L_H);                        //遍历合并后的链表

    DestroyList_cycle(L_T);                         //销毁第二个链表

    return 0;
}