循環(huán)鏈表是頭尾相接的鏈表。循環(huán)鏈表的最后一個節(jié)點的指針
域指向鏈表的頭結(jié)點或首元結(jié)點（沒有頭結(jié)點的情況下）。
下圖是有頭結(jié)點的單向循環(huán)鏈表：

單向循環(huán)鏈表

雙向循環(huán)鏈表：

雙向循環(huán)鏈表

通過以下內(nèi)容來學(xué)習(xí)單向循環(huán)鏈表的使用：
1. 單向循環(huán)列表的創(chuàng)建-尾插法
2. 單向循環(huán)列表的插入
3. 單向循環(huán)列表的刪除
4. 單向循環(huán)列表的查詢

注意??！本文中代碼使用沒有頭結(jié)點的單向循環(huán)列表演示，第一個結(jié)點是列表的首元結(jié)點。

• 兩種創(chuàng)建方式的區(qū)別：使用頭結(jié)點的單向循環(huán)鏈表，鏈表指針指向頭結(jié)點不會改變，在插入和刪除結(jié)點的操作中，不用移動鏈表的指針。而不使用頭結(jié)點則需要根據(jù)結(jié)點位置來判斷是否需要移動鏈表的指針，較為復(fù)雜。
• 定義單向循環(huán)鏈表的結(jié)構(gòu)體結(jié)點：

#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0

typedef int Status;//狀態(tài)值
typedef int ElemType;//結(jié)點的數(shù)據(jù)類型，視實際情況而定。在此以int為例。

//定義結(jié)點
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node *LinkList;

1. 單向循環(huán)列表的創(chuàng)建

以尾插法創(chuàng)建單向循環(huán)鏈表有以下幾步：
① 判斷鏈表為空則創(chuàng)建鏈表；
② 為首元結(jié)點賦值，并將指針域指向本身；
③ 不為空則創(chuàng)建新結(jié)點，并找到當前列表的尾結(jié)點，將新結(jié)點設(shè)置為尾結(jié)點。
代碼如下：

//創(chuàng)建單向循環(huán)列表
Status CreateList(LinkList *L) {
    
    ElemType item;
    
    LinkList temp,tail;
    
    printf("請輸入結(jié)點的值，輸入0結(jié)束:\n");
    
    while (1) {
        
        scanf("%d",&item);
        
        if (item == 0) break;
        
        if (*L == NULL) {//第一次創(chuàng)建
            *L = (LinkList)malloc(sizeof(Node));
            if (!L) return ERROR;
            (*L)->data = item;
            (*L)->next = *L;
            
            //標記尾結(jié)點
            tail = *L;
        }else {
            temp = (LinkList)malloc(sizeof(Node));
            //健壯性
            if (!temp) return ERROR;
            temp->data = item;
            temp->next = *L;
            tail->next = temp;
            
            tail = temp;
        }
    }
    return OK;
}

以上代碼，使用臨時變量tail記錄尾結(jié)點，也可以遍歷查找尾結(jié)點。但是從時間復(fù)雜度分析，該算法的時間復(fù)雜度為O(1)，如果使用循環(huán)查找，時間復(fù)雜度為O(n)耗費使用臨時變量更好。

2. 單向循環(huán)列表的插入

插入結(jié)點分為兩種不同的情況，一種是在首元結(jié)點的位置插入新結(jié)點，另一種是在其他位置插入新結(jié)點。

• 在首元結(jié)點位置插入新結(jié)點的步驟：
  ① 創(chuàng)建新結(jié)點，指針域指向首元結(jié)點；
  ② 找到尾結(jié)點，尾結(jié)點指針域指向新結(jié)點；
  ③ 鏈表頭指針指向新結(jié)點。
• 在其他位置插入新結(jié)點的步驟：
  ① 找到插入位置的前一個結(jié)點target；
  ② 創(chuàng)建一個新的結(jié)點，指針域指向target的下一個結(jié)點；
  ③ target的指針域指向新結(jié)點。
  代碼如下：

Status InsertNode(LinkList *L) {
    
    int place;
    ElemType item;
    LinkList temp,target;

    printf("請輸入插入新結(jié)點的位置:\n");
    scanf("%d",&place);
    if (place < 1) {
        printf("請輸入大于0的位置:\n");
        scanf("%d",&place);
    }
    
    printf("請輸入插入新結(jié)點的值:\n");
    scanf("%d",&item);
        
    //在首元結(jié)點位置插入,設(shè)這里鏈表結(jié)點位置從1開始
    if (place == 1) {
        /*插如到首元結(jié)點需要做的事
            1.創(chuàng)建新結(jié)點，指針域指向首元結(jié)點；
            2.找到尾結(jié)點，尾結(jié)點指針域指向新結(jié)點；
            3.鏈表頭指針指向新結(jié)點。
         */
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) return ERROR;
        temp->data = item;
        temp->next = *L;
        //尋找尾結(jié)點tail
        for (target = *L; target->next != *L; target = target->next);
        
        target->next = temp;
        
        *L = temp;
    }else {//在其他結(jié)點位置插入
        /*插入到其他位置需要做的事：
            1.找到插入位置的前一個結(jié)點target；
            2.創(chuàng)建一個新的結(jié)點，指針域指向target的下一個結(jié)點；
            3.`target`的指針域指向新結(jié)點。
         */
        //循環(huán)，找到插入位置place的前一個結(jié)點
        target = *L;
        int I;
        for (i = 1; target->next != *L && i != place-1; i++) {
            target = target->next;
        }
        //判斷place
        if (place > i && target->next == *L) {
            printf("輸入的位置太大了\n");
            return ERROR;
        }
        
        temp = (LinkList)malloc(sizeof(Node));
        temp->data = item;
        temp->next = target->next;
        
        target->next = temp;
    }
    return OK;
}

3. 單向循環(huán)列表的刪除

刪除結(jié)點分為兩種不同的情況，一種是在刪除首元結(jié)點，另一種是刪除其他位置的結(jié)點。

• 刪除首元結(jié)點需要做的事情：
  ①找到尾結(jié)點，尾結(jié)點的指針域指向首元結(jié)點的下一個結(jié)點；
  ②鏈表指針指向首元結(jié)點的下一個結(jié)點；
  ③釋放原來的首元結(jié)點。
• 刪除其他結(jié)點需要做的事情：
  ①找到刪除位置的前一個結(jié)點target；
  ②保存刪除位置的結(jié)點；
  ③target的指針域指向刪除位置的下一個結(jié)點；
  ④釋放刪除位置的結(jié)點。
  代碼如下：

Status DeletNode(LinkList *L){
    int place;
    LinkList temp,target = NULL;

    printf("請輸入刪除結(jié)點的位置:\n");
    scanf("%d",&place);
    if (place < 1) {
        printf("請輸入大于0的位置:\n");
        scanf("%d",&place);
    }
    
    if (place == 1) {//刪除首元結(jié)點,位置從1開始
        /*刪除首元結(jié)點需要做的事情：
         ①找到尾結(jié)點，尾結(jié)點的指針域指向首元結(jié)點的下一個結(jié)點；
            ②鏈表指針指向首元結(jié)點的下一個結(jié)點；
            ③釋放原來的首元結(jié)點。
        */
        //判斷當鏈表中只有1個結(jié)點時，直接鏈表指針
        if((*L)->next == (*L)){
            (*L) = NULL;
            return OK;
        }
        //記錄首元結(jié)點
        temp = *L;
        
        for (target = *L; target->next != *L; target = target->next) ;
        
        *L = (*L)->next;
        
        target->next = *L;
        
        free(temp);
        
    }else {//刪除其他結(jié)點
        /*刪除其他結(jié)點需要做的事情：
            ①找到刪除位置的前一個結(jié)點target；
            ②保存刪除位置的結(jié)點；
            ③target的指針域指向刪除位置的下一個結(jié)點；
            ④釋放刪除位置的結(jié)點。
        */
        int I;
        target = *L;
        for (i = 1; target->next != *L && i != place-1; i++) {
            target = target->next;
        }
        
        if (place > i && target->next == *L) {
            printf("輸入的位置太大了\n");
            return ERROR;
        }
        temp = target->next;

        target->next = temp->next;
        
        free(temp);
    }
    return OK;
}

4. 單向循環(huán)列表的查詢

循環(huán)查找單向循環(huán)鏈表L中值為value的結(jié)點：

int findValue(LinkList L,int value){
    
    int i = 1;
    LinkList p;
    p = L;
    
    //尋找鏈表中的結(jié)點 data == value
    while (p->data != value && p->next != L) {
        I++;
        p = p->next;
    }
    
    //當尾結(jié)點指向頭結(jié)點就會直接跳出循環(huán),所以要額外增加一次判斷尾結(jié)點的data
    if (p->next == L && p->data != value) {
        return  -1;//返回沒有找到
    }
    
    return i;//返回找到的位置
}