如何使用遞歸和非遞歸方式反轉(zhuǎn)單向鏈表
更新時(shí)間：2013年07月19日 12:16:08 作者：
以下是對(duì)使用遞歸和非遞歸方式反轉(zhuǎn)單向鏈表的示例進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過來參考下
問題：
給一個(gè)單向鏈表，把它從頭到尾反轉(zhuǎn)過來。比如： a -> b -> c ->d 反過來就是 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 的值，否則我們無法繼續(xù)。所以，我們需要兩個(gè)指針分別指向前一個(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è)問題也可以通過遞歸的方式解決。代碼如下：
復(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 的值沒有改變，為該鏈表的最后一個(gè)node，所以，反轉(zhuǎn)后，我們可以得到新鏈表的head。
相關(guān)文章
詳解C++編程中用數(shù)組名作函數(shù)參數(shù)的方法
這篇文章主要介紹了詳解C++編程中用數(shù)組名作函數(shù)參數(shù)的方法,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09
如何使用C語言實(shí)現(xiàn)細(xì)菌的繁殖與擴(kuò)散
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)細(xì)菌的繁殖與擴(kuò)散，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章主要為大家詳細(xì)介紹了C語言的位段與枚舉，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
C語言計(jì)算器的3種實(shí)現(xiàn)方法代碼
這篇文章主要給大家介紹了關(guān)于C語言計(jì)算器的3種實(shí)現(xiàn)方法,文中通過代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一的參考借鑒價(jià)值,需要的朋友可以參考下2007-01-01
學(xué)習(xí)C++以來還沒有總結(jié)過C++的大括號(hào)的使用方式,所以這篇文章主要來和大家介紹一下C++中大括號(hào)的用法合集,需要的小伙伴可以參考一下2024-12-12
C++實(shí)現(xiàn)的大數(shù)相乘算法示例
這篇文章主要介紹了C++實(shí)現(xiàn)的大數(shù)相乘算法,結(jié)合實(shí)例形式分析了C++大數(shù)相乘的概念、原理及代碼實(shí)現(xiàn)技巧,需要的朋友可以參考下2017-08-08
本篇文章是C語言編程篇，主要為大家介紹C語言編程中當(dāng)Const遇上指針的分析講解，有需要的朋友可以借鑒參考下，希望可以有所幫助2021-09-09
這篇文章主要為大家詳細(xì)介紹了C語言員工業(yè)績銷售源代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-11-11
使用Qt封裝一個(gè)發(fā)送http請(qǐng)求通用類
這篇文章主要為大家詳細(xì)介紹了如何使用Qt封裝一個(gè)通用類,可以通過QNetworkRequest和QNetworkReply進(jìn)行http請(qǐng)求,感興趣的可以了解一下2024-12-12
C/C++實(shí)現(xiàn)通訊錄管理系統(tǒng)(附源碼)
這篇文章主要為大家詳細(xì)介紹了如何利用C++實(shí)現(xiàn)通訊錄管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-12-12