C++實現反轉鏈表的兩種方法

更新時間：2023年02月09日 11:11:37 作者：努力進大廠的新青年

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

一.使用vector容器

ps：該方法對內存的需求較高，這是個缺點，可以直接使用STL容器自帶的reverse進行反轉(將vector容器內的結點進行反轉，然后再用for循環(huán)將他串聯起來)，實現起來相對容易，思路不太復雜。

請看以下代碼：

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()); // 反轉vector，也可以逆向遍歷
        ListNode *head = v[0];
        ListNode *cur = head;
        for (int i=1; i<v.size(); ++i) { // 構造鏈表
            cur->next = v[i]; // 當前節(jié)點的下一個指針指向下一個節(jié)點
            cur = cur->next; // 當前節(jié)點后移
        }
        cur->next = nullptr; // 切記最后一個節(jié)點的下一個指針指向nullptr
        return head;
    }
};

此方法的復雜度：

時間復雜度：O(n)

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

二.調整指針法

ps：此方法更加妥當，能得到更多人的青睞，很好的利用幾個指針的指向反轉一個鏈表。

初始化：3個指針

1）pre指針指向已經反轉好的鏈表的最后一個節(jié)點，最開始沒有反轉，所以指向nullptr

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

3）nex指針指向待反轉鏈表的第二個節(jié)點，目的是保存鏈表，因為cur改變指向后，后面的鏈表則失效了，所以需要保存

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

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

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

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

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

循環(huán)結束后，cur當然為nullptr，所以返回pre，即為反轉后的頭結點

這里以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;
    }
};

此方法復雜度：

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

空間復雜度：O(1)

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

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

您可能感興趣的文章: