今天，我們來解決一個問題吧！

給定一個遞增的鏈結串列，回傳一個遞減的鏈結串列。

其實，這個問題有兩個解決方法！

1. 將原本鏈結串列的數值儲存於陣列中，再將它們以遞減的形式儲存在新建立的鏈結串列中。
2. 翻轉原本的鏈結串列

試試看第一種方法！

SLLNode *reverse(SLLNode *head) {
    std::vector <int> temp;
    SLLNode *cur = head;
    while (cur) {
        temp.push_back(cur -> data);
        cur = cur -> next;
    }
    cur = head;
    for (int i=temp.size()-1; i>=0; i--) {
        cur -> data = temp[i];
        cur = cur -> next;
    }
    return head;
}

這個方法確實可以達到效果，但是我們需要再使用一個空間來完成這件事情。

第二種方法，我們就直接對鏈結串列作翻轉，並將它設為一個類別方法。

定義類別

class SLL {
private:
    SLLNode *head;
public:
    SLL();
    void pushFront(int);
    void printAll();
    int popFront();
    void pushBack(int);
    int popBack();
    void insert(int);
    void remove(int);
    void reverse();
};

class DLL {
private:
    DLLNode *head, *tail;
public:
    DLL();
    void pushFront(int);
    void printAll();
    int popFront();
    void pushBack(int);
    int popBack();
    void insert(int);
    void remove(int);
    void reverse();
};

單向鏈結串列

這個方法所遇到的兩個問題是

1. 當我們將 cur -> next 指定給前一個節點後，我們從此無法再取得他的下一個節點，因此我們需要將它紀錄起來。
2. 當 cur 被更改為 cur -> next，我們無法再取得前一個節點，因為這是一個「單向」的鏈結串列，因此我們要將前一個節點記錄下來。

剩下的部分就是如何設計迴圈了！

void SLL::reverse()
{
    SLLNode *prev = NULL;
    SLLNode *cur = this -> head;
    SLLNode *next;
    while (cur != NULL)
    {
        next = cur -> next;
        cur -> next = prev;
        prev = cur;
        cur = next;
    }
    this -> head = prev;
}

雙向鏈結串列

作法與單向鏈結串列的相同，要特別注意雙向指標的鏈結與 head, tail 的位置為何。

void DLL::reverse()
{
    DLLNode *prev = NULL;
    DLLNode *cur = this -> head;
    DLLNode *next;
    this -> tail = this -> head;
    while (cur != NULL)
    {
        next = cur -> next;
        cur -> next = prev;
        cur -> prev = next;
        prev = cur;
        cur = next;
    }
    this -> head = prev;
}

鏈結串列的實作其實有很多，許多時候只要將圖畫出來，答案就很明顯啦！

下一篇開始，我們將進到新的主題：樹