如何使用遞歸和非遞歸方式反轉單向鏈表

2020-01-26 15:59:10

字體：大中小

來源：轉載

供稿：網友

問題：
給一個單向鏈表，把它從頭到尾反轉過來。比如： 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。

上一篇：VC6.0常見鏈接錯誤與解決方法

下一篇：linux c 獲得當前進程的進程名和執行路徑(示例)