資料結構篇：單循環連結清單倒置（帶頭結點/不帶頭結點）

帶頭結點

先去看一下單連結清單的倒置：https://blog.csdn.net/qq_15020543/article/details/84590642

對于單循環連結清單，它與單連結清單差別是，它的最後一個結點将指向頭結點（無頭結點将指向第一個結點），構成一個循環.

周遊循環連結清單的時候，結束标志是next指向head

了解了這些基礎概念，單循環連結清單的倒置也不難了

完整函數

Inode *Test::ReserveLink(Inode *h) {
    Inode *HeadNext, *HeadPre, *firstNode;
    HeadNext = h->next->next;
    HeadPre = h->next;
    firstNode = h->next;//儲存第一個結點的引用
    while (HeadNext != h)
    {
        Inode *tempNode = HeadNext->next;
        HeadNext->next = HeadPre;
        HeadPre = HeadNext;
        if (tempNode == h)
        {
            h->next = HeadPre;
        }
        HeadNext = tempNode;
    }
    //将最初的第一個結點，指向現在的頭結點
    firstNode->next = h;
    return h;
}
           

 完整程式

#include <iostream>

using namespace std;

typedef struct Link {
    int num;
    Link *next;
} Inode;

class Test {
public :
    Inode *t_CreateList(Inode *Head, int n);//尾插法建立單循環連結清單
    void ShowLink(Inode *h);

    Inode *ReserveLink(Inode *h);
};

Inode *Test::t_CreateList(Inode *Head, int n) {
    Inode *p = Head;
    for (int i = 0; i < n; i++)
    {
        Inode *s = new Inode;
        cin >> s->num;
        s->next = p->next;
        p->next = s;
        p = s;
    }
    return Head;
}


void Test::ShowLink(Inode *h) {
    Inode *p = h;
    cout << "單循環連結清單為：" << endl;
    while (p->next != h)
    {
        cout << p->next->num << "-->";
        p = p->next;
    }
    cout << endl;
}

Inode *Test::ReserveLink(Inode *h) {
    Inode *HeadNext, *HeadPre, *firstNode;
    HeadNext = h->next->next;
    HeadPre = h->next;
    firstNode = h->next;//儲存第一個結點的引用
    while (HeadNext != h)
    {
        Inode *tempNode = HeadNext->next;
        HeadNext->next = HeadPre;
        HeadPre = HeadNext;
        if (tempNode == h)
        {
            h->next = HeadPre;
        }
        HeadNext = tempNode;
    }
    //将最初的第一個結點，指向現在的頭結點
    firstNode->next = h;
    return h;
}

int main() {
    Test test;
    Inode *Head = new Inode;
    Head->next = Head;
    int num;
    cout << "您想要建立幾個元素的單循環連結清單？請輸入：" << endl;
    cin >> num;
    Head = test.t_CreateList(Head, num);
    test.ShowLink(Head);
    Head = test.ReserveLink(Head);
    test.ShowLink(Head);
    return 0;
}
           

運作截圖

不帶頭結點

Inode *Test::ReserveLink(Inode *h) {
    Inode *HeadNext, *HeadPre, *firstNode;
    HeadNext = h->next;
    HeadPre = h;
    firstNode = h;//儲存第一個結點的引用
    while (HeadNext != h)
    {
        Inode *tempNode = HeadNext->next;
        HeadNext->next = HeadPre;
        HeadPre = HeadNext;
        if (tempNode == h)
        {
            h = HeadPre;
        }
        HeadNext = tempNode;
    }
    //将最初的第一個結點，指向現在的頭結點
    firstNode->next = h;
    return h;
}