线性表之单循环链表

单链表必须从头结点出发才能访问全部节点。

为了解决这个问题，将单链表中的终结点的指针从NULL改为指向头结点，这就形成了一个环，头尾相接的单链表叫单循环链表，简称循环链表。

注意：循环链表与单链表的主要差异在空链表的判断上：

种类	空链表	非空链表
循环链表	head->next == head	head->next != head
单链表	head->next == null	head->next != null

终结点使用尾指针rear指示，则开始结点（元素的第一个）为rear->next->next，首末结点查找都是O(1)。

注意以下几点：

1）循环链表是一个“环”，每个结点都是概念上都是对等的，这里没有单链表中那个空的头结点，唯一不同的是链表名也就是头指针指向谁谁就是第一个结点。当改变第一个结点时，不要忘了改变头指针（代码34行）。

2）区分node pNode，node *pNode，node **pNode。第一个pNode是一个结点，从栈中申请的结点，如果在子函数中，函数结束返回后会被释放，不可以把它加到链表中。第二个*pNode是一个结点的指针，也就是链表（可以考虑为结点的数组名），如果next为null也可以认为是从堆中申请的一个结点（包含一个结点的链表）。第三个**pNode是一个链表的指针，如果想在函数之间传递参数并且修改这个链表（如插入删除），要传这个链表指针。如果传递参数但是不希望修改（如遍历或者计算长度），可以传第二个。

详细代码如下：

#include<iostream>
using namespace std;
///**************循环链表**********************/

typedef struct CLinkList
{
    int data;
    struct CLinkList *next;
}node;

//插入结点
//参数：链表的指针，插入的位置
void CList_insert(node **pNode, int i)
{
    node *temp;
    node *target;

    int item;
    target = *pNode;
    cout<<"请输入您要插入的值"<<endl;
    cin>>item;
    if(i == 1)
    {
        //创建一个新结点加入到链表
        temp = new node;
        temp->data = item;
        //找到最后一个结点，注意判断条件
        while(target->next != (*pNode))
        {
            target = target->next;
        }
        temp->next = (*pNode);
        target->next = temp;
        *pNode = temp;
    }
    else{
        int j = 1;
        //找到要插入的前一个结点
        while( j<i-1 )
        {
            target = target->next;
            ++j;
        }
        temp = new node;
        //插入
        temp->data = item;
        temp->next = target->next;
        target->next = temp;
    }
}

//初始化循环链表
void CList_init(node **pNode)
{
    int item;
    node *temp;
    node *target;

    cout<<"输入结点的值，输入0完成初始化"<<endl;

    while(1)
    {
        cin>>item;
        if(item == 0)
            return;
        if((*pNode) == NULL)
        {//插入第一个结点
            (*pNode) = new node;
            if(!(*pNode))
                exit(0);
            (*pNode)->data = item;
            (*pNode)->next = *pNode; //循环的定义
        }
        else
        {
            target = *pNode;
            while(target->next != (*pNode)) //找到最后一个结点（指向第一个）
            {
                target = target->next;
            }
            temp = new node;
            if(!temp)
                exit(0);
            //这是插入到最后一个位置！！！
            //看pNode指向谁谁是头
            temp->data = item;
            temp->next = *pNode;
            target->next = temp;
        }
    }
}

//删除指定结点
void CList_delete(node **pNode, int i)
{
    node *temp;
    node *target;
    target = *pNode;
    if(i == 1) //删除第一个结点
    {
        //找到最后一个结点，注意判断条件
        while(target->next != (*pNode))
        {
            target = target->next;
        }
        temp = (*pNode);
        target->next = temp;
        *pNode =  (*pNode)->next;
        target->next = *pNode;
        delete temp;
    }
    else{
        int j = 1;
        //找到要删除的前一个结点
        while( j<i-1 )
        {
            target = target->next;
            ++j;
        }
        //删除
        temp = target->next;
        target->next = temp->next;
        delete temp;
    }
}

//返回指定值的结点所在位置
int CList_search(node *pNode, int elem)
{
    node *target = pNode;
    int i = 1;
    //
    while(target->next != (pNode) && target->data != elem) //找到最后一个结点（指向第一个）
    {
            target = target->next;
            i++;
    }
        //不存在这个元素
    if(target->data != elem)
        return 0;
    else
        return i;
}

//遍历元素
void CList_traverse(node *pNode)
{
    node *temp;
    temp = pNode;
    cout<<"链表中的元素为"<<endl;
    do
    {
        cout<<temp->data<<"  ";
    }while((temp = temp->next) != pNode);

    cout<<endl;
}

int main()
{
    node *pHead = NULL;
    char opp;
    int findval;
    cout<<" 1、初始化链表 \n 2、插入结点 \n 3、删除结点 \n 4、返回结点位置 \n 5、遍历链表 \n 0、退出"<<endl;
    while(opp != '0')
    {
        cin>>opp;
        switch(opp)
        {
        case '1':
            CList_init(&pHead);
            cout<<endl;
            CList_traverse(pHead);
            break;
        case '2':
            cout<<"请输入需要插入的结点位置"<<endl;
            cin>>findval;
            CList_insert(&pHead, findval);
            cout<<"插入后为"<<endl;
            CList_traverse(pHead);
            break;
        case '3':
            cout<<"请输入要删除结点的位置"<<endl;
            cin>> findval;
            CList_delete(&pHead, findval);
            cout<<"删除后为："<<endl;
            CList_traverse(pHead);
            cout<<endl;
            break;
        case '4':
            cout<<"你要查找的结点值为？"<<endl;
            cin>>findval;
            cout<<"元素位于："<<CList_search(pHead, findval);
            cout<<endl;
            break;
        case '5':
            CList_traverse(pHead);
            cout<<endl;
            break;
        case '0':
            exit(0);
        }
    }
    return 0;
}

使用rear指针指向链表的尾端，称为尾指针表示的循环链表。

则头结点为rear->next,降低了查找最后一个结点 的复杂度，O(n)->O(1)，在把两个链表接在一起时候，容易实现。

如何判断单链表是否有环，两个方法：

1）使用两个指针，一个指针p1每走一步，另一个指针p2从头开始遍历，直到p2找到一个结点的地址与p1指向的结点地址相同为止，此时比较他们两个所经历的步数，如果相同则break，若是不同那我们就找到了环！

int existLoop1(node *L)
{
    node *cur1 = L;
    int pos1 = 0;

    while(cur1)   //cur1结点存在
    {
        node* cur2 = L;
        int pos2 = 0;
        while(cur2)  //cur2结点存在
        {
            if(cur2 == cur1)   //如果指向同一个地址，判断步数
            {
                if(pos1 == pos2)  //此时步数相同则无环，否则有环
                    break;
                else
                {
                    cout<<"环的位置在"<<pos2<<"个结点处"；
                    return 1;
                }
            }
            cur2 = cur2->next;  //cur1每动一次，cur2结点直到找到一个与其相同的或者到空
            pos2++;
        }
        cur1 = cur1->next;  //cur1每次动一个位置
        pos1++;
    }
    return 0;
}

2）使用快慢指针，一个指针每次走两步，另一个每次走一步，总有一天快的会追上慢的，这样可以判断有环没环（没环就指向NULL了）。

int existLoop2(node* L)
{
    node* p_fast = L;
    node* p_slow = L;

    while(p_fast != NULL && p_slow != NULL && p_fast->next != NULL)
    {
        p_slow = p_slow->next;
        if(p_fast->next != NULL)
            p_fast = p_fast->next->next;

        cout<<"p_fast"<<p_fast->data<<"p_slow"<<p_slow->data<<endl;

        if(p_fast == p_slow)
            return 1;
    }
    return 0;
}