在鏈接列表中反向打印

Question

我想編寫函數在Java中打印鏈接列表的反轉。我這樣寫，但它不起作用。編譯器警告NullPointerException。

void ReversePrint(Node head) { 
    int[] array = null; 
    int i = 0; 
    Node tmp; 
    for (tmp = head; tmp != null; tmp = tmp.next) { 
     array[i] = tmp.data; 
     i++; 
    } 
    for(int j = i; j >= 0; j--){ 
     System.out.println(array[j]); 
    } 
} 

Answer 1

你得到NullPointerException因爲變量array是null：

int[] array = null; 

你需要你在這裏使用它之前與價值首先初始化：

array[i] = tmp.data; 

例如像這樣的陳述：

int[] array = new int[size]; 

其中size應該是您的LinkedList的大小。如果你不知道尺寸，你可以使用ArrayList類，它實現了動態尺寸（它猜測一個尺寸，如果你超過它，它會重新分配一個更大的數組，並複製所有內容結束等等）。

下面是使用一個版本說ArrayList：

// Method names should start with a lower-case letter 
void reversePrint(Node head) { 
    // Initialize an empty ArrayList 
    ArrayList<Integer> dataList = new ArrayList<>(); 
    int i = 0; 
    Node tmp; 
    for (tmp = head; tmp != null; tmp = tmp.next) { 
     // Set the element at position i of the ArrayList 
     dataList.set(i, tmp.data); 
     i++; 
    } 

    // See next comment 
    i--; 

    for(int j = i; j >= 0; j--){ 
     // Get the element at position j of ArrayList and print it 
     System.out.println(dataList.get(j)); 
    } 
} 

---

注意，你也會遇到IndexOutOfBoundException，因爲你i是1以達到大印刷循環時。這是因爲你在第一循環的最後一次迭代也增加了它：

// Suppose last iteration, i is (list.size() - 1) then 
for (tmp = head; tmp != null; tmp = tmp.next) { 
    array[i] = tmp.data; 
    // i is now list.size() 
    i++; 
} 

你需要在環路初始化的環路之間的一個i--或int j = i - 1。

---

如果要實現雙鏈接列表，而不是隻單鏈接列表，則請注意，您不需要故事值數組第一。然後您可以直接從tail和tmp.prev指針開始打印值。

Answer 2

要做到這一點，最簡單的方法是使用遞歸方法：

void ReversePrint(Node node) { 
    if (node != null) { 
     ReversePrint(node.next); 
     System.out.println(node.data); 
    } 
}