如何使用遞歸和非遞歸方式反轉(zhuǎn)單向鏈表？問(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ù)制代碼

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

問(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 valueNode 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) {//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}上面代碼使用的是非遞歸方式，這個(gè)問(wèn)題也可以通過(guò)遞歸的方式解決。代碼如下：復(fù)制代碼代碼如下:public Node reverse(Node current){if (current == null || current.next == null) return currentNode nextNode = current.nextcurrent.next = nullNode reverseRest = reverse(nextNode)return reverseRest}遞歸的方法其實(shí)是非常巧的，它利用遞歸走到鏈表的末端，然后再更新每一個(gè)node的next 值 (代碼倒數(shù)第二句)。

Java語(yǔ)言寫出實(shí)現(xiàn)將單向鏈表順序反轉(zhuǎn)的函數(shù)？

假設(shè)鏈表的節(jié)點(diǎn)定義如下:class Node{int iNode next}那么其反轉(zhuǎn)函數(shù)為: void reverse(Node l){if(l==null) returnNode p=null，q=l，r=l.nextwhile(r!=null){q.next=pp=qq=rr=r.next}q.next=pl=q}