大家好，今天和大家分享的是反轉(zhuǎn)鏈表的兩種方法，第一種是用泛型編程里面的STL，第二種是利用多個(gè)指針進(jìn)行操作，小孩子才做選擇，建議兩個(gè)都學(xué)。我們往下看：

一.使用vector容器

ps：該方法對(duì)內(nèi)存的需求較高，這是個(gè)缺點(diǎn)，可以直接使用STL容器自帶的reverse進(jìn)行反轉(zhuǎn)(將vector容器內(nèi)的結(jié)點(diǎn)進(jìn)行反轉(zhuǎn)，然后再用for循環(huán)將他串聯(lián)起來)，實(shí)現(xiàn)起來相對(duì)容易，思路不太復(fù)雜。

請(qǐng)看以下代碼：

typedef struct Node
{
 int val;
  struct Node*next;
 
}ListNode;
 
class traverse {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (!pHead) return nullptr;
        vector<ListNode*> v;
        while (pHead) {
            v.push_back(pHead);
            pHead = pHead->next;
        }
        reverse(v.begin(), v.end()); // 反轉(zhuǎn)vector，也可以逆向遍歷
        ListNode *head = v[0];
        ListNode *cur = head;
        for (int i=1; i<v.size(); ++i) { // 構(gòu)造鏈表
            cur->next = v[i]; // 當(dāng)前節(jié)點(diǎn)的下一個(gè)指針指向下一個(gè)節(jié)點(diǎn)
            cur = cur->next; // 當(dāng)前節(jié)點(diǎn)后移
        }
        cur->next = nullptr; // 切記最后一個(gè)節(jié)點(diǎn)的下一個(gè)指針指向nullptr
        return head;
    }
};
 

此方法的復(fù)雜度：

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n), 用了一個(gè)vector來存單鏈表

二.調(diào)整指針法

ps：此方法更加妥當(dāng)，能得到更多人的青睞，很好的利用幾個(gè)指針的指向反轉(zhuǎn)一個(gè)鏈表。

初始化：3個(gè)指針

1）pre指針指向已經(jīng)反轉(zhuǎn)好的鏈表的最后一個(gè)節(jié)點(diǎn)，最開始沒有反轉(zhuǎn)，所以指向nullptr

2）cur指針指向待反轉(zhuǎn)鏈表的第一個(gè)節(jié)點(diǎn)，最開始第一個(gè)節(jié)點(diǎn)待反轉(zhuǎn)，所以指向head

3）nex指針指向待反轉(zhuǎn)鏈表的第二個(gè)節(jié)點(diǎn)，目的是保存鏈表，因?yàn)閏ur改變指向后，后面的鏈表則失效了，所以需要保存

接下來，循環(huán)執(zhí)行以下三個(gè)操作

1）nex = cur->next, 保存作用

2）cur->next = pre 未反轉(zhuǎn)鏈表的第一個(gè)節(jié)點(diǎn)的下個(gè)指針指向已反轉(zhuǎn)鏈表的最后一個(gè)節(jié)點(diǎn)

3）pre = cur， cur = nex; 指針后移，操作下一個(gè)未反轉(zhuǎn)鏈表的第一個(gè)節(jié)點(diǎn)

循環(huán)條件，當(dāng)然是cur != nullptr

循環(huán)結(jié)束后，cur當(dāng)然為nullptr，所以返回pre，即為反轉(zhuǎn)后的頭結(jié)點(diǎn)

這里以1->2->3->4->5 舉例：

代碼如下：

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *pre = nullptr;
        ListNode *cur = pHead;
        ListNode *nex = nullptr; // 這里可以指向nullptr，循環(huán)里面要重新指向
        while (cur) {
            nex = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nex;
        }
        return pre;
    }
};

此方法復(fù)雜度：

時(shí)間復(fù)雜度：O(n), 遍歷一次鏈表

空間復(fù)雜度：O(1)

總結(jié)：要從易懂的角度來看，第一種不失是好的，使用STL，我現(xiàn)在才大一，我聽說一些面試是不允許使用STL這一內(nèi)容解體的。第二種方法很妙，復(fù)雜度是比較理想的，而且用到了靈魂指針的應(yīng)用。建議大家多琢磨一下第二種方法。