时间复杂度O(n^2)空间复杂度O(n^2)
感觉函数行参给少了，多给两个形参，一个是大小，一个是初始化好的数组引用，时间空间复杂度能降到O(n)。只有一个形参代码写的很难受。
”’java
//从尾头打印链表，使用递归
public class Solution {
public int[] reversePrint(ListNode head)
{
if(head null)
return new int[0];
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
if head == None:
return []
# val = []
# while head != None:
# val.append(head.val)
# head = head.next
# return val[::-1]
if head.next == None:
return [head.val]
val = []
for i in self.reversePrint(head.next):
val.append(i)
val.append(head.val)
return val
#python解题
class Solution(object):
def reversePrint(self, head):
“””
:type head: ListNode
:rtype: List[int]
“””
if not head:
return []
count = 0
cur = head
while cur:
count += 1
cur = cur.next
res = [0] * count
k = count -1
while head:
res[k] = head.val
k -= 1
head = head.next
return res
class Solution {
public int[] reversePrint(ListNode head) {
int n = 0;
ListNode pre = head;
while(head!=null){head = head.next;n++;}
int[] list = new int[n];
if(pre == null){
return list;
}
for(int i = 0; i
class Solution {
public:
vector reversePrint(ListNode* head) {
traverse(head);
return res;
}
int len = 0; // for initialize len of vector
vector res; // store the return value
int p = 0; // record the index of the current position in vector
void traverse(ListNode* head) {
if (head == nullptr) {
res.resize(len);
return;
}
len++;
traverse(head->next);
res[p] = head->val;
p++;
}
};
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
if (head==null){
return new int[0];
}
List<Integer> list = new ArrayList<>();
process(head,list);
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i]=list.get(i);
}
return res;
}
public static void process(ListNode head,List<Integer> list){
if (head==null){
return;
}
process(head.next,list);
list.add(head.val);
}
}
shuaidi
共以下 41 个回答
打卡成功！
/** reverseBookList(ListNode head) { res;
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
vector
recur(head);
return res;
}
private:
std::vector
void recur(ListNode* head)
{
if (head nullptr)
{
return;
}
recur(head->next);
res.push_back(head->val);
}
};
时空复杂度都是 O(n)
判空–>计算长度–>申请堆区空间–>数组从后往前接收值–>返回。（注意：C语言解题时需将长度赋值给returnSize）
“””
int* reversePrint(struct ListNode* head, int* returnSize){
// 判空
// if (head NULL) {
// return NULL;
// }
int count = 0;
struct ListNode* tmp_list = head;
// 计算链表长度
while (tmp_list != NULL) {
count++;
tmp_list = tmp_list->next;
}
}
“””
剑指 Offer 06. 从尾到头打印链表
> Problem: 剑指 Offer 06. 从尾到头打印链表
[TOC]
思路
解题方法
解题方法1
时间复杂度： $O(n)$
空间复杂度： $O(n)$
解题方法2+3
递归法
递归的空间复杂度与使用栈的空间复杂度是一致的，所以需要使用非递归的方法进行优化
时间复杂度： $O(n)$
空间复杂度： $O(n)$
非递归法
时间复杂度： $O(n)$
空间复杂度： $O(1)$
解题方法4+5
//有三种方式 res(count)
//1 使用栈 2 使用反转链表 递归和原地 3 使用数组反向遍历 从右向左遍历
//一共四种方法 前两个时间和空间复杂度都为O(n) 后面两个时间为O(n) 空间为O(1)
if(head NULL)
return{};
int count=0;
ListNode *temp =head;
while(temp )
{
count++;
temp = temp->next;
}
vector
int k = count-1;
while(head)
{
res[k–] = head->val;
head= head->next;
}
return res;
栈先进后出（判断栈为空：empty()）
时间复杂度：O(n) 空间复杂度：O(n)
时间O(n)，空间O(1)
class Solution {
public int[] reversePrint(ListNode head) {
//统计链表长度
int length=0;
for(ListNode l=head;l!=null;l=l.next){
length++;
}
//创建数组
int[] res=new int[length];
//把链表数值倒序存储到数组中（链表第一个对应数组第length-1个，i->length-i）
ListNode l=head;
for(int i=1;i<=length;i++,l=l.next){
res[length-i]=l.val;
}
return res;
}
}
/** reversePrint(ListNode head) {a = reversePrint(head->next);
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector
if(headNULL) return {};
vector
a.push_back(head->val);
return a;
}
};
时间复杂度：o(N)
空间复杂度:O(1)
// 递归方式打印链表
void printListReversely(ListNode* head) {
if (head NULL) {
return;
}
时间复杂度o（n），空间复杂度o（n）
打卡
class Solution {
public int[] reversePrint(ListNode head) {
ListNode temp = head;
int count = 0;
while(temp != null){
temp = temp.next;
count++;
}
int[] arr = new int[count];
int k = count – 1;
while(head != null){
arr[k–] = head.val;
head = head.next;
}
return arr;
}
}
打卡
//首先通过遍历将每一个节点都塞入vector中； reversePrint(ListNode* head) { vec;
//然后再将通过reverse函数将里面的节点顺序掉换；
//时间复杂度为o(n);
//空间复杂度为o(n);
class Solution {
public:
vector
vector
ListNode *p=head;
while(head){
vec.push_back(head->val);
head=head->next;
}
reverse(vec.begin(),vec.end());
return vec;
};
空间复杂度：o(m)，时间复杂度：o(m)
时间复杂度：o(n)，空间复杂度：o(n) reversePrint(ListNode* head) { stk; ans;
思路：创建一个栈，先遍历链表将元素压入栈中，后将栈中的元素依次弹出放入到数组中。
class Solution {
public:
vector
stack
vector
while (head != NULL) {
stk.push(head->val);
head = head->next;
}
};
/** result; reversePrint(ListNode head) { res(count);
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
vector
public:
vector
/if(head!=NULL){
reversePrint(head->next);
result.push_back(head->val);
}
return result;/递归 时间复杂度O(n) 空间复杂度O(n)
int count=0;
ListNode *t=head;
while(t!=NULL){
t=t->next;
count++;
}
vector
while(head != NULL){
res[–count] = head->val;
head = head->next;
}//从右往左遍历 时间复杂度O(n) 空间复杂度O(1)
return res;
}
};
递归方法时间和空间复杂度都为O(N)
思路：先统计链表长度，再定义一个等同大小的数组，遍历链表依次从后往前添加到数组中
时间复杂度：O(n)，空间复杂度：O(n)
class Solution {
public int[] reversePrint(ListNode head) {
if(head null) {
return new int[0];
}
ListNode cur = head;
int length = 0;
while(cur != null) {
length++;
cur = cur.next;
}
int[] result = new int[length];
cur = head;
for(int i = length – 1; i >= 0; –i) {
result[i] = cur.val;
cur = cur.next;
}
return result;
}
}
时间复杂度O(n^2)空间复杂度O(n^2)
感觉函数行参给少了，多给两个形参，一个是大小，一个是初始化好的数组引用，时间空间复杂度能降到O(n)。只有一个形参代码写的很难受。
”’java
//从尾头打印链表，使用递归
public class Solution {
public int[] reversePrint(ListNode head)
{
if(head null)
return new int[0];
}
时间O（n） 空间O(n)
时间复杂度O（n）
空间复杂度O（n）
先遍历一遍链表获得长度
再创建对应长度的数组
遍历第二遍插入数组就行
ector reversePrint(ListNode* head) {{}; nullptr){ tmp; ans = reversePrint(head->next);
if(head nullptr){
return vector
}
if(head->next
vector
tmp.emplace_back(head->val);
return tmp;
}
递归实现
vector
ans.emplace_back(head->val);
#python解题
class Solution(object):
def reversePrint(self, head):
“””
:type head: ListNode
:rtype: List[int]
“””
if not head:
return []
/**
*打卡
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
if(head null)
return new int[0];
}
class Solution { result; reversePrint(ListNode* head) {
vector
public:
vector
if(head){
reversePrint(head->next);
result.push_back(head->val);
}
return result;
}
};
时间复杂度O(n)，空间复杂度O(1)
两个方法
+ 方法一：使用递归实现
时间复杂度O(N)，空间复杂度O(1)
时间复杂度：O(N),空间复杂度：O(1)
本题是主要是思考如何使用递归，我第一版本代码思路错了，想着的时候何时append，想着的是尾结点的时候才append第一个，然后根据root.next为空在append，但实际上没必要做任何判断，只需要在后序位置appned即可。
时间复杂度：O(N),空间复杂度：O(1)
先由链表长度确定数组长度，再把数字以相反的排列存放在数组中
时间On 空间On
遍历存储值到vector; reversePrint(ListNode head) { vec;
反转vector；
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector
vector
auto *p = head;
while (p != nullptr) {
vec.emplace_back(p->val);
p = p->next;
}
reverse(vec.begin(), vec.end());
return vec;
}
};
1、迭代遍历
思路：利用栈存储节点值，出栈到数组返回
时间复杂度O(n)，空间复杂度O(n)
“`python
Definition for singly-linked list.
class ListNode:
def init(self, x):
self.val = x
self.next = None
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
#先用栈写
#对于每个节点，压入栈（push(node))
#然后循环出栈，出栈的每个节点存入数组
# res = []
# s = []
# i=0
# while head:
# i+=1
# s.append(head.val)
# head = head.next
“`python
//c 获得链表长度，动态创建数组，赋值数组，反向输出；
int* reversePrint(struct ListNode* head, int* returnSize){
struct ListNode* p1=head;
int i=0;
while(p1){
i++;
p1=p1->next;
}
returnSize=i;
int ans=(int)malloc(isizeof(int));
int n=i-1;
p1=head;
while(p1){
ans[n–]=p1->val;
// *(ans+i)=p1->val; //倒序将链表元素放入数组
// i–;
p1=p1->next;
}
free(p1) ;
return ans;
}
使用递归，深度遍历
時間複雜度 O(n) 空間複雜度 O(n)
利用遞歸鏈表中的後序遍歷來反向儲存鏈表中的值,
时间复杂度O(n),空间复杂度O(n)
时间复杂度O(n),空间复杂度O(n)