快捷導(dǎo)航

C++實(shí)現(xiàn)反轉(zhuǎn)鏈表的兩種方法

更新時(shí)間：2023年02月09日 11:11:37 作者：努力進(jìn)大廠的新青年

本文主要介紹了C++實(shí)現(xiàn)反轉(zhuǎn)鏈表的兩種方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

一.使用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)用。建議大家多琢磨一下第二種方法。

到此這篇關(guān)于C++實(shí)現(xiàn)反轉(zhuǎn)鏈表的兩種方法的文章就介紹到這了,更多相關(guān)C++ 反轉(zhuǎn)鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: