欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2023年02月09日 11:11:37   作者:努力進大廠的新青年  
本文主要介紹了C++實現(xiàn)反轉(zhuǎn)鏈表的兩種方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧

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

一.使用vector容器

ps:該方法對內(nèi)存的需求較高,這是個缺點,可以直接使用STL容器自帶的reverse進行反轉(zhuǎn)(將vector容器內(nèi)的結(jié)點進行反轉(zhuǎn),然后再用for循環(huán)將他串聯(lián)起來),實現(xià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()); // 反轉(zhuǎn)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來存單鏈表

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

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

初始化:3個指針

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

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

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

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

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

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

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

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

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

這里以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)

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

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

相關文章

  • 詳情介紹C++之命名空間

    詳情介紹C++之命名空間

    這篇文章主要詳情介紹了C++命名空間,命名空間的出現(xiàn)就是為了解決名稱沖突問題,對此感興趣的朋友可以參考下面文章
    2021-09-09
  • C語言實現(xiàn)學生選修課程系統(tǒng)設計

    C語言實現(xiàn)學生選修課程系統(tǒng)設計

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)學生選修課程系統(tǒng)設計,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-02-02
  • C++中cin的返回值問題

    C++中cin的返回值問題

    這篇文章主要介紹了C++中cin的返回值問題,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-07-07
  • C++?opencv學習之圖像像素的邏輯操作

    C++?opencv學習之圖像像素的邏輯操作

    圖像的像素操作包括讀寫操作、算數(shù)操作、邏輯運算操作等,下面這篇文章主要給大家介紹了關于C++?opencv學習之圖像像素的邏輯操作的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下
    2022-11-11
  • Opencv開發(fā)實現(xiàn)拼圖游戲

    Opencv開發(fā)實現(xiàn)拼圖游戲

    這篇文章主要為大家詳細介紹了Opencv開發(fā)實現(xiàn)拼圖游戲,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-07-07
  • 成員初始化列表與構造函數(shù)體中的區(qū)別詳細解析

    成員初始化列表與構造函數(shù)體中的區(qū)別詳細解析

    無論是在構造函數(shù)初始化列表中初始化成員,還是在構造函數(shù)體中對它們賦值,最終結(jié)果是相同的。不同之處在于,使用構造函數(shù)初始化列表的版本初始化數(shù)據(jù)成員,沒有定義初始化列表的構造函數(shù)版本在構造函數(shù)體中對數(shù)據(jù)成員賦值
    2013-09-09
  • C++采用ring3讀取MBR實例

    C++采用ring3讀取MBR實例

    這篇文章主要介紹了C++采用ring3讀取MBR實例,可實現(xiàn)對硬盤的主引導記錄的讀取,非常具有實用價值,需要的朋友可以參考下
    2014-10-10
  • c語言簡單實現(xiàn)文件 r/w 操作方法

    c語言簡單實現(xiàn)文件 r/w 操作方法

    由于在 C 語言中 '\' 一般是轉(zhuǎn)義字符的起始標志,故在路徑中需要用兩個 '\' 表示路徑中目錄層次的間隔,也可以使用 '/' 作為路徑中的分隔符,本文重點給大家介紹用c語言簡單實現(xiàn)文件 r/w 操作方法,感興趣的朋友一起學習吧
    2021-05-05
  • c++ 對數(shù)器實現(xiàn)示例

    c++ 對數(shù)器實現(xiàn)示例

    對數(shù)器用于在自己的本地平臺驗證算法正確性,本文詳細的介紹了c++ 對數(shù)器實現(xiàn),文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-08-08
  • ipv6實現(xiàn)udp編程示例

    ipv6實現(xiàn)udp編程示例

    這篇文章主要介紹了ipv6實現(xiàn)udp編程示例,需要的朋友可以參考下
    2014-03-03

最新評論