C++實現(xiàn)LeetCode(206.倒置鏈表)
[LeetCode] 206.Reverse Linked List 倒置鏈表
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
之前做到 Reverse Linked List II 的時候我還納悶怎么只有二沒有一呢，原來真是忘了啊，現(xiàn)在才加上，這道題跟之前那道比起來簡單不少，題目為了增加些許難度，讓我們分別用迭代和遞歸來實現(xiàn)，但難度還是不大。我們先來看迭代的解法，思路是在原鏈表之前建立一個空的newHead，因為首節(jié)點會變，然后從head開始，將之后的一個節(jié)點移到newHead之后，重復(fù)此操作直到head成為末節(jié)點為止，代碼如下：
解法一：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *newHead = NULL;
while (head) {
ListNode *t = head->next;
head->next = newHead;
newHead = head;
head = t;
}
return newHead;
}
};
下面我們來看遞歸解法，代碼量更少，遞歸解法的思路是，不斷的進(jìn)入遞歸函數(shù)，直到head指向倒數(shù)第二個節(jié)點，因為head指向空或者是最后一個結(jié)點都直接返回了，newHead則指向?qū)ead的下一個結(jié)點調(diào)用遞歸函數(shù)返回的頭結(jié)點，此時newHead指向最后一個結(jié)點，然后head的下一個結(jié)點的next指向head本身，這個相當(dāng)于把head結(jié)點移動到末尾的操作，因為是回溯的操作，所以head的下一個結(jié)點總是在上一輪被移動到末尾了，但head之后的next還沒有斷開，所以可以順勢將head移動到末尾，再把next斷開，最后返回newHead即可，代碼如下：
解法二：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
};
到此這篇關(guān)于C++實現(xiàn)LeetCode(206.倒置鏈表)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)倒置鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C語言庫函數(shù)中的內(nèi)存操作函數(shù)memcpy()、memmove()、memset()、memcmp()使用示例分析，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-09-09
這篇文章主要介紹了C++為什么非要引入那幾種類型轉(zhuǎn)換,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
淺談c++如何實現(xiàn)并發(fā)中的Barrier
這篇文章主要介紹了淺談c++如何實現(xiàn)并發(fā)中的Barrier，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
C語言里可以用#define定義一個標(biāo)識符來表示一個常量。特點是：定義的標(biāo)識符不占內(nèi)存，只是一個臨時的符號，預(yù)編譯后這個符號就不存在了，也不做類型定義。預(yù)編譯又叫預(yù)處理2022-04-04
這篇文章主要介紹了C++中引用&與取地址&的區(qū)別,有助于C++初學(xué)者更好的掌握指針的概念及用法,需要的朋友可以參考下2014-09-09
C++中數(shù)組作為函數(shù)參數(shù)傳入的幾種方式代碼示例
數(shù)組元素和數(shù)組名都可以作為函數(shù)的參數(shù)以實現(xiàn)函數(shù)間數(shù)據(jù)的傳遞和共享,下面這篇文章主要給大家介紹了關(guān)于C++中數(shù)組作為函數(shù)參數(shù)傳入的幾種方式,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-06-06
PIMPL 是 C++ 中的一個編程技巧，意思為指向?qū)崿F(xiàn)的指針。具體操作是把類的實現(xiàn)細(xì)節(jié)放到一個單獨的類中，并用一個指針進(jìn)行訪問2022-07-07
今天小編就為大家分享一篇關(guān)于C語言測試n的階乘和x的n次方，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-02-02
分支結(jié)構(gòu)的執(zhí)行是依據(jù)一定的條件選擇執(zhí)行路徑，而不是嚴(yán)格按照語句出現(xiàn)的物理順序。分支結(jié)構(gòu)的程序設(shè)計方法的關(guān)鍵在于構(gòu)造合適的分支條件和分析程序流程，根據(jù)不同的程序流程選擇適當(dāng)?shù)姆种дZ句2022-05-05
在類中 只有靜態(tài)變量能賦值 如果你不賦值 編譯器會認(rèn)為你這個變量根本沒用 不能被修改 又沒有初始值 兩個辦法 在構(gòu)造函數(shù)的初始化列表賦值 或者在const前面加一個static2015-07-07