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