輸入一個(gè)鏈表的頭節(jié)點(diǎn)，從尾到頭反過(guò)來(lái)返回每個(gè)節(jié)點(diǎn)的值（用數(shù)組返回）尼变。
示例 1
輸入：head = [1,3,2]
輸出：[2,3,1]
限制：
0 <= 鏈表長(zhǎng)度 <= 10000
思路1
如果允許更改結(jié)構(gòu), 那么可以先把鏈表反轉(zhuǎn),在順序打印,此時(shí)不需額外的空間
class Solution {
public int[] reversePrint(ListNode head) {
if (head == null) return new int[0];
ListNode tmp = head;
ListNode next = tmp.next;
tmp.next = null;
int size = 1;
while (tmp != null && next != null) {
ListNode tt = next.next;
next.next = tmp;
tmp = next;
next = tt;
size++;
}
int[] result = new int[size];
for (int i = 0; i < size; i++) {
result[i] = tmp.val;
tmp = tmp.next;
}
return result;
}
}
反轉(zhuǎn)鏈表的經(jīng)典操作
ListNode tmp = head;
ListNode next = tmp.next;
tmp.next = null;
while (tmp != null && next != null) {
ListNode nn = next.next;
next.next = tmp;
tmp = next;
next = nn;
}
思路2
如果不允許修改鏈表,那么可以使用一個(gè)棧來(lái)存儲(chǔ)節(jié)點(diǎn),然后先入后出,同時(shí)由椑眨可以想到遞歸,遞歸本身也是一個(gè)棧.
class Solution {
public int[] reversePrint(ListNode head) {
if (head == null) return new int[0];
int size = 0;
ListNode tmp = head;
while(tmp != null) {
size++;
tmp = tmp.next;
}
int[] result = new int[size];
// 開(kāi)始遞歸
tmp = head;
recur(result, tmp, size - 1);
return result;
}
private void recur(int[] result, ListNode node, int index) {
if (node == null) return;
recur(result, node.next, index - 1);
result[index] = node.val;
}
}
