若何應用遞歸和非遞歸方法反轉單向鏈表。本站提示廣大學習愛好者：（若何應用遞歸和非遞歸方法反轉單向鏈表）文章只能為提供參考，不一定能成為您想要的結果。以下是若何應用遞歸和非遞歸方法反轉單向鏈表正文
成績：
給一個單向鏈表，把它從頭至尾反轉過去。好比： a -> b -> c ->d 反過去就是 d -> c -> b -> a 。
剖析：
假定每個node的構造是：
class Node {
char value;
Node next;
}
由於在對鏈表停止反轉的時刻，須要更新每個node的“next”值，然則，在更新 next 的值前，我們須要保留 next 的值，不然我們沒法持續。所以，我們須要兩個指針分離指向前一個節點和後一個節點，每次做完以後節點“next”值更新後，把兩個節點往下移，直到達到最初節點。
代碼以下：
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 值 (代碼倒數第二句)。 在下面的代碼中， reverseRest 的值沒有轉變，為該鏈表的最初一個node，所以，反轉後，我們可以獲得新鏈表的head。
