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ù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
成員初始化列表與構造函數(shù)體中的區(qū)別詳細解析
無論是在構造函數(shù)初始化列表中初始化成員,還是在構造函數(shù)體中對它們賦值,最終結(jié)果是相同的。不同之處在于,使用構造函數(shù)初始化列表的版本初始化數(shù)據(jù)成員,沒有定義初始化列表的構造函數(shù)版本在構造函數(shù)體中對數(shù)據(jù)成員賦值2013-09-09