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