如何使用遞歸和非遞歸方式反轉(zhuǎn)單向鏈表？問題：給一個單向鏈表，把它從頭到尾反轉(zhuǎn)過來。比如： a - b - c -d 反過來就是 d - c - b - a 。分析：假設(shè)每一個node的結(jié)構(gòu)是：復(fù)制代碼

如何使用遞歸和非遞歸方式反轉(zhuǎn)單向鏈表？

問題：給一個單向鏈表，把它從頭到尾反轉(zhuǎn)過來。比如： a - b - c -d 反過來就是 d - c - b - a 。分析：假設(shè)每一個node的結(jié)構(gòu)是：復(fù)制代碼代碼如下:class Node {char valueNode next}因為在對鏈表進行反轉(zhuǎn)的時候，需要更新每一個node的“next”值，但是，在更新 next 的值前，我們需要保存 next 的值，否則我們無法繼續(xù)。所以，我們需要兩個指針分別指向前一個節(jié)點和后一個節(jié)點，每次做完當(dāng)前節(jié)點“next”值更新后，把兩個節(jié)點往下移，直到到達最后節(jié)點。代碼如下：復(fù)制代碼代碼如下:public Node reverse(Node current) {//initializationNode previousNode = nullNode nextNode = nullwhile (current != null) {//save the next nodenextNode = current.next//update the value of "next"current.next = previousNode//shift the pointerspreviousNode = currentcurrent = nextNode}return previousNode}上面代碼使用的是非遞歸方式，這個問題也可以通過遞歸的方式解決。代碼如下：復(fù)制代碼代碼如下:public Node reverse(Node current){if (current == null || current.next == null) return currentNode nextNode = current.nextcurrent.next = nullNode reverseRest = reverse(nextNode)return reverseRest}遞歸的方法其實是非常巧的，它利用遞歸走到鏈表的末端，然后再更新每一個node的next 值 (代碼倒數(shù)第二句)。