反轉鏈表？

Question

代碼的工作原理是我的講師遞給我的，我不會見他4個星期，我沒有人去爲此。 我需要了解它是如何工作的，以及代碼的一部分。

import java.util.LinkedList; 

public class Reverse { 

public static void main(String[] args) { 
    // TODO Auto-generated method stub 

    LinkedList<String> names = new LinkedList<String>(); 
    names.add("Ceri"); 
    names.add("Jesus"); 
    names.add("Abigail"); 

    Reverse(names); 
} 

public static void Reverse(LinkedList<String> list){ 

    System.out.println("->" + list); 

    if(list.size() > 1){ 
     String s = list.removeLast(); 
     Reverse(list); 
     list.addFirst(s); 
    } 
    System.out.println(list); 
} 

}

該位要準確：

if(list.size() > 1){ 
     String s = list.removeLast(); 
     Reverse(list); 
     list.addFirst(s); 
    } 
    System.out.println(list); 
} 

我進入調試模式，看看哪些被處決線和list.addFirst(s)只有當list.size() > 1是，即使它在錯誤的執行爲塊。 此外，它遍歷兩次分配小號「阿比蓋爾」和「耶穌」來小號但是當運行list.addFirst(s)，它彷彿小號的作用就像一個數組？

很難解釋我的意思，如果你通過eclipse和調試模式運行它，你會明白我的意思。

Answer 1

這是一個遞歸函數。需要list.size()檢查，因爲您需要遞歸函數的基本情況。它確保如果列表中只有一個項目，那麼不要對它做任何事情。

基本上，它開始像這樣

Ceri, Jesus, Abigail 

當反向調用函數時，它看到有3個項目，所以它存儲阿比蓋爾在S（我們稱之爲S1）注意函數ISN」 t完成了，它會再次調用Reverse。

你有名單Ceri, Jesus，而你的S1是Abigail。在這裏調用Reverse，S（讓它叫做S2）現在是Jesus。這個功能還沒有完成，因爲它必須調用Reverse。

該列表現在只有Ceri，所以當它被調用時，它停止（只有1項）。讓我們回到了函數調用，（從最近稱爲第一），你看到S2被添加到列表的前面，所以現在的名單看起來像

Jesus, Ceri 

然後，添加S1。

Abigail, Jesus, Ceri。瞧！反向列表！

Answer 2

該算法的本質是遞歸的。它指出（並使其發生）列表的反面是：

If the list is longer than 1 entry (a 1-entry list is its own reverse) 
1. Remove the last entry. 
2. Reverse the remaining list. 
3. Add the removed item onto the start of the list. 

Answer 3

Reverse方法是遞歸的（它自己調用），這似乎讓你感到困惑。考慮到您的具體起始列表，該方法將遞歸兩次，總共三次調用，每次調用都有其自己的單獨局部變量集。雖然每個遞歸都會傳遞list參數，儘管每個調用都有自己的該變量副本，但它們都引用相同的對象。

這裏發生了什麼故障：

• 初始呼叫
  • list.size()最初3
  • 元"Abigail"被取出，並在局部變量s（這個堆棧幀）
  • 舉行第一次遞歸
    • list.size()最初是2，一元素已被刪除
    • 元素"Jesus"被刪除並保存在本地變量s的這個棧幀;這是不一樣的變量作爲初始呼叫的幀
    • 第二遞歸
      • list.size()最初1，已經由先前的每個Reverse()調用的（尚未返回均未）除去一個元件
      • 的列表未被修改。 "Ceri"是此時它唯一的元素。
    • 第二遞歸返回
    • 該幀的s（"Jesus"）被添加到列表的前面，得到（"Jesus"，"Ceri"）
  • 第一遞歸返回
  • 該幀的s （"Abigail"）被添加到列表的前面以產生（"Abigail", "Jesus", "Ceri"）