从尾到头打印链表
题目描述：
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）
解题思路
列表 + 反转法
- 遍历链表的同时，用列表保存其值，然后反转列表即可
- 时间复杂度：
O(n)，空间复杂度：O(n)
class Solution {
public int[] reversePrint(ListNode head) {
List<Integer> l = new ArrayList<>();
while (head != null) {
l.add(head.val);
head = head.next;
}
Collections.reverse(l);
return l.stream().mapToInt(Integer::valueOf).toArray();
}
栈
- 基本操作
- 时间复杂度：
O(n)，空间复杂度：O(n)
class Solution {
public int[] reversePrint(ListNode head) {
Deque<Integer> stack = new ArrayDeque<>();
int count = 0;
while (head != null) {
count++;
stack.push(head.val);
head = head.next;
}
int idx = 0, ans[] = new int[count];
while (idx < count) {
ans[idx++] = stack.pop();
}
return ans;
}
反转链表法
- 将链表进行反转，然后遍历得到结果，如果需要的话，最后再将链表进行还原
- 时间复杂度：
O(n)，空间复杂度：O(1)（不包含返回值int[]所占空间）
class Solution {
int count;
public int[] reversePrint(ListNode head) {
head = reverse(null, head, head);
ListNode cur = head;
int idx = 0, ans[] = new int[count];
while (cur != null) {
ans[idx++] = cur.val;
cur = cur.next;
}
head = reverse(null, head, head);
return ans;
}
private ListNode reverse(ListNode pre, ListNode next, ListNode cur) {
count = 0;
while (cur != null) {
count++;
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
知识点
-
List调用toArray(T[])方法转换为数组时，这里T代表泛型，泛型必须为引用类型。所以不能这样list.toArray(new int[0])，但可以这样list.toArray(new int[0][0])，因为int[]时引用类型。如果要将list转为维度为(3, 2)的数组，不需要这样list.toArray(new int[3][2])，可以但没有必须，使用list.toArray(new int[0][0])执行速度更快。详情看参考链接 - Java 中一般使用
ArrayDeque双向队列来模拟栈，而不用Stack，原因大概有：-
Stack继承于Vector，是 Java 早期的产物，里面有很多冗余的方法，使用不方便。且被遗弃，JAVA 官方也不推荐使用此类 - 很多方法都用了
synchronized修饰符，虽然保证了线程安全，但效率会很低。一般场景下使用ArrayDeque即可，如果在需要保证线程安全时，使用Collections.synchronizedCollection()将其转换为线程安全的即可
-
-
Collections.reverse(List<?> list)核心操作：以中心为轴，交换对称的元素
ListIterator fwd = list.listIterator();
ListIterator rev = list.listIterator(size);
for (int i=0, mid=list.size()>>1; i<mid; i++) {
Object tmp = fwd.next();
fwd.set(rev.previous());
rev.set(tmp);
}
参考链接
List (或ArrayList) 转换为int[]数组 终于搞懂了
Java中List, Integer[], int[]的相互转换
You should use toArray(new T[0]) instead of toArray(new T[size]).
