剑指 Offer 06. 从尾到头打印链表
本问题对应的 leetcode 原文链接:剑指 Offer 06. 从尾到头打印链表
本文对应打卡链接:【链表专题】剑指 Offer 06. 从尾到头打印链表
问题描述
输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
示例 1:
输入:head = [1,3,2]
输出:[2,3,1]
限制:
0 <= 链表长度 <= 10000
解题思路
视频讲解直达: 本题视频讲解
代码实现
// 从右边=往左填充
public int[] reversePrint(ListNode head) {
if(head == null)
return new int[0];
// 统计链表节点个数,方便创建数组
int count = 0;
ListNode temp = head;
while(temp != null){
count++;
temp = temp.next;
}
int[] res = new int[count];
int k = count - 1;
// 从由往左填充数组
while(head != null){
res[k--] = head.val;
head = head.next;
}
return res;
}
时间复杂度:O(n)
额外空间复杂度:O(1)
评论(7)
public int[] reversePrint(ListNode head) {
int len = 0;
ListNode cur = head;
while(cur != null){
cur = cur.next;
len++;
}
int[] a = new int[len];
int num = 1;
cur = head;
while(cur != null){
a[len-num] = cur.val;
num++;
cur = cur.next;
}
return a;
}
时间复杂度:O(n)
额外空间复杂度:O(1)
“`java
class Solution {
public int[] reversePrint(ListNode head) {
//方法一 创建指针遍历得到链表的长度 新建一个数组 从尾开始增加链表的值 注意数组的长度和元素的下表不要出错!!
if(head == null){
return new int[0];
}
int count = 0;
ListNode temp = head;
while(temp!=null){
temp = temp.next;
count++;
}
int [] res = new int[count];
int k = count -1;
while(head!=null){
res[k–] = head.val;
head = head.next;
}
return res;
//方法二:利用栈先进后处的特点来完成 stack.add()增加元素 stack.pop()弹出栈内最上面的元素 st = new Stack ();
Stack
int count = 0;
while(head!=null){
st.add(head.val);
head = head.next;
}
int [] res = new int[st.size()];
for(int i =0; i <res.length; i++){
res[i] = st.pop();
}
return res;
}
}
递归。但是list怎么能直接取出数组?
复杂度分析:
时间复杂度:O(n)
空间复杂度:O(1)
思路一:先反转链表,再遍历,这样就不需要额外的栈空间开销
方法二:使用栈
方法三:就地逆序数组