如何使用遞歸和非遞歸方式反轉(zhuǎn)單向鏈表
更新時間：2013年07月19日 12:16:08 作者：
以下是對使用遞歸和非遞歸方式反轉(zhuǎn)單向鏈表的示例進行了詳細的分析介紹，需要的朋友可以過來參考下
問題：
給一個單向鏈表，把它從頭到尾反轉(zhuǎn)過來。比如： a -> b -> c ->d 反過來就是 d -> c -> b -> a 。
分析：
假設每一個node的結(jié)構(gòu)是：
復制代碼 代碼如下:
class Node {
char value;
Node next;
}
因為在對鏈表進行反轉(zhuǎn)的時候，需要更新每一個node的“next”值，但是，在更新 next 的值前，我們需要保存 next 的值，否則我們無法繼續(xù)。所以，我們需要兩個指針分別指向前一個節(jié)點和后一個節(jié)點，每次做完當前節(jié)點“next”值更新后，把兩個節(jié)點往下移，直到到達最后節(jié)點。
代碼如下：
復制代碼 代碼如下:
public Node reverse(Node current) {
//initialization
Node previousNode = null;
Node nextNode = null;
while (current != null) {
//save the next node
nextNode = current.next;
//update the value of "next"
current.next = previousNode;
//shift the pointers
previousNode = current;
current = nextNode;
}
return previousNode;
}
上面代碼使用的是非遞歸方式，這個問題也可以通過遞歸的方式解決。代碼如下：
復制代碼 代碼如下:
public Node reverse(Node current)
{
if (current == null || current.next == null) return current;
Node nextNode = current.next;
current.next = null;
Node reverseRest = reverse(nextNode);
nextNode.next = current;
return reverseRest;
}
遞歸的方法其實是非常巧的，它利用遞歸走到鏈表的末端，然后再更新每一個node的next 值 (代碼倒數(shù)第二句)。 在上面的代碼中， reverseRest 的值沒有改變，為該鏈表的最后一個node，所以，反轉(zhuǎn)后，我們可以得到新鏈表的head。
相關(guān)文章
繞線畫簡單點來說，就是在木板上釘一圈釘子，通過繞線進行構(gòu)圖，最終呈現(xiàn)出一幅圖像。本文將用C語言實現(xiàn)這一效果，感興趣的小伙伴可以嘗試一下2022-11-11
這篇文章主要介紹了C語言基礎知識分享續(xù)篇的相關(guān)資料,需要的朋友可以參考下2023-01-01
C++常量詳解二(常量形參，常量返回值，常量成員函數(shù))
這篇文章主要介紹了C++常量詳解二(常量形參，常量返回值，常量成員函數(shù)),需要的朋友可以參考下2017-06-06
在本篇文章里小編給大家分享的是一篇關(guān)于C/C++中的atan和atan2函數(shù)實例用法相關(guān)內(nèi)容，有興趣的朋友們可以學習下。2020-02-02
這篇文章主要介紹C++ 參數(shù)的三種傳遞方式和應用場景，C++ 參數(shù)的三種傳遞方式分別是值傳遞、指針傳遞和引用傳遞，感興趣的同學可以參考閱讀下2023-06-06
這篇文章主要給大家介紹了關(guān)于C++深淺拷貝和寫時拷貝的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04
這篇文章主要介紹了使用C語言求N的階乘的方法,包括一道相關(guān)的ACM題目示例,需要的朋友可以參考下2015-08-08
在C++17中實現(xiàn)無鎖數(shù)據(jù)結(jié)構(gòu)的方法詳解
在探索?C++17?中的無鎖數(shù)據(jù)結(jié)構(gòu)之前,我們首先需要理解無鎖編程的基本概念及其在現(xiàn)代軟件開發(fā)中的重要性,在這個章節(jié)中,我們將深入探討無鎖編程的概念,以及它如何滿足人類對于更高效、更可靠軟件的本能需求,文中通過代碼示例介紹的非常詳細,感興趣的朋友可以參考下2023-12-12
這篇文章主要介紹了c++ string的erase刪除方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12
這篇文章主要介紹了C語言實現(xiàn)天氣信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-06-06