【链表专题】剑指 Offer 06. 从尾到头打印链表

本问题对应课程链接：剑指offer刷题第七期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 2 年前 207 52

共以下 51 个回答

為愛而生普通 2024年12月23日下午2:41

时On^2 空On
class Solution {
public int[] reverseBookList(ListNode head) {
ListNode cnt = head;
int count = 0;
while (cnt != null) {
cnt = cnt.next;
count++;
}
ListNode p = head;
int num = count;
int[] array = new int[count];
for (int j = 0; j < count; j++) {
for(int i = 1; i <= num – 1; i++)
p = p.next;
array[j] = p.val;
num –;
p = head;
}
return array;
}
}

0 赞同 0 条回复

登录以回复

桃桃摇摇奶昔° 普通 2024年12月3日下午7:37

class Solution {
    public int[] reverseBookList(ListNode head) {
        if(head <span class="text-highlighted-inline" style="background-color: #fffd38;"> 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;
    }
}

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日上午2:13

/**
方法一：
反转在打印，需遍历两次，时间复杂度O(N)
方法二：
递归，遍历一次，时间复杂度O(N)
方法三：
栈，入栈遍历一次，出栈遍历一次，总两次，时间复杂度O(N)，需要额外空间O(N)
 */
class Solution {

    List<Integer> res;
    public int[] reverseBookList(ListNode head) {
        res = new ArrayList<>();
        helper(head);
        int[] ans = new int[res.size()];
        for (int i = 0; i < res.size(); i++){
            ans[i] = res.get(i);
        }
        return ans;


    }

    public void helper(ListNode node){
        if (node == null){
            return;
        }
        helper(node.next);
        res.add(node.val);
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年11月28日下午11:05

打卡

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
        if not head:
            return []
        return self.reverseBookList(head.next) + [head.val]

0 赞同 0 条回复

mpweixin用户普通 2024年11月28日下午11:05

打卡

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
        if not head:
            return []
        return self.reverseBookList(head.next) + [head.val]

0 赞同 0 条回复

mpweixin用户普通 2024年11月28日下午11:05

打卡

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
        if not head:
            return []
        return self.reverseBookList(head.next) + [head.val]

0 赞同 0 条回复

mpweixin用户普通 2024年11月28日下午11:05

打卡

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
        if not head:
            return []
        return self.reverseBookList(head.next) + [head.val]

0 赞同 0 条回复

mpweixin用户普通 2024年11月28日下午11:05

打卡

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
        if not head:
            return []
        return self.reverseBookList(head.next) + [head.val]

0 赞同 0 条回复

Carry on 普通 2024年11月28日上午10:08

// 答案
public static int[] reverseBookList(ListNode head) {
Stack stack = new Stack<>();
int len = 0;
ListNode p = head;
while (p != null){
stack.push(p.val);
p = p.next;
len++;
}
int[] result = new int[len];
int index = 0;
while (!stack.isEmpty()){
result[index++] = stack.pop();
}
return result;
}

0 赞同 0 条回复

登录以回复

Lil Lee_ 普通 2024年11月27日下午2:34

//辅助栈法
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] reverseBookList(ListNode head) {

        LinkedList<Integer> stack = new LinkedList<Integer>();
        while(head != null){
            stack.addLast(head.val);
            head = head.next;
        }
        int[] res = new int [stack.size()];
        for(int i =0 ; i < res.length; i++)
            res[i] = stack.removeLast();
    return res;

    }
}

//递归
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reverseBookList(ListNode head) {
        recur(head);
        int[] res = new int[tmp.size()];
        for(int i = 0; i < res.length; i++){
            res[i] = tmp.get(i);
        }
        return res;    
    }
    void recur(ListNode head){
        if(head == null) return;
        recur(head.next);
        tmp.add(head.val);
    }
}

0 赞同 0 条回复

前方有星云普通 2024年11月27日上午12:23
class Solution {
public int[] reverseBookList(ListNode head) {
Stack stack = new Stack<>();
ListNode cur = head;
while(cur!=null){
stack.push(cur);
cur=cur.next;
}
int s = stack.size();
int[] num = new int[s];
for(int i=0;i<s;i++){
num[i]=stack.pop().val;
}
```
    return num;

}
```
}
利用栈，还是太菜了。时间复杂度O（n);空间复杂度O(n)
0 赞同 0 条回复

登录以回复

陆狗陆狗普通 2024年11月26日下午10:49

题解（遍历2次，第一次获取链表长度，第二次把值倒序放到数组里面）

class Solution {
    public int[] reverseBookList(ListNode head) {
        if(head==null){
            // 【错误点1】
            return new int[0];
        }
        // 统计链表长度
        ListNode tmpt=head;
        int size=0;
        while(tmpt!=null){
            size++;
            tmpt=tmpt.next;
        }
        // 创建数组存储（倒序存放）
        int[] result=new int[size];
        while(head!=null){
            // 【错误点2】
            result[--size]=head.val;
            head=head.next;
        }
        // 打印数组
        return result;
    }
}

错误点1：如果为null，需要返回空数组而不是null
错误点2：size–记得是return扣减之前的值，再进行–操作。

0 赞同 0 条回复

树懒在橘子洲数星星普通 2024年11月26日下午8:41

“`python
//递归直至节点为空，然后逐层加入节点值进行返回
class Solution(object):
def reverseBookList(self, head):
if head:
return self.reverseBookList(head.next)+[head.val]
else:
return []
时间复杂度：O(N) N为链表长度
空间复杂度：O(N) 系统递归需要使用的栈空间

0 赞同 0 条回复

登录以回复
hjx 普通 2024年11月26日下午3:29

class Solution {
public int[] reverseBookList(ListNode head) {
if(headnull) return new int[0];
Stackstack=new Stack<>();
while(head!=null){
stack.push(head.val);
head=head.next;
}
int[] ans=new int[stack.size()];
int index=0;
while(!stack.isEmpty()){
ans[index++]=stack.pop();
}
return ans;
}
}
时间：O(n), 空间O(n)

0 赞同 0 条回复

登录以回复

ㅤ牛马学编程普通 2024年11月26日上午12:41

“`
class Solution {
public int[] reverseBookList(ListNode head) {
if (head == null) {
// 链表为空时,返回一个空的数组
return new int[0];
}

    // 统计数组链表长度
    int count = 0;
    ListNode temp = head;
    while (temp != null) {
        count++;
        temp = temp.next;
    }

    // 定义新数组用于返回
    int[] newArr = new int[count];
    while (head != null) {
        newArr[count - 1] = head.val;
        count--;
        head = head.next;
    }
    return newArr;
}

}

0 赞同 0 条回复

yelinliner 普通 2024年11月25日下午6:18

###

class Solution {
    public int[] reverseBookList(ListNode head) {
        // 非空判断
        if (head == null)
            return new int[0];
        int count = 0;
        // 链表长度
        ListNode temp = head;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        // new 数组
        int[] result = new int[count];
        int index = count - 1;
        // 遍历链表 倒序给数组赋值
        while (head != null) {
            result[index] = head.val;
            index--;
            head = head.next;
        }
        return result;
    }
}

时间复杂度O(n)；空间复杂度O(n)

0 赞同 0 条回复

无言永久会员 2024年11月24日下午1:43

/**
 * 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<int> res;
    void recur(ListNode* head) {
        if(head == nullptr) return;
        recur(head->next);
        res.push_back(head->val);
    }
    vector<int> reverseBookList(ListNode* head) {
        recur(head);
        return res;
    }
};
时间复杂度: O(N) 
空间复杂度: O(N)

0 赞同 0 条回复

捕风永久会员 2024年11月24日上午10:18

方法1、用栈辅助，利用先进后出的特性，但是时间复杂度和空间复杂度都是O(n)
方法2、反转链表【方法一：递归（O(n)）；方法二：原地反转，性能好，但容易错】，再顺序遍历存到数组中
方法3、遍历数组改为New一个数组，从右到左遍历，时间复杂度O(n)，空间复杂度O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] reverseBookList(ListNode head) {
        // 判断链表是否为空
        if(head == null)return new int[0];

        int count = 0;  // 统计节点个数
        ListNode temp = head;  
        while(temp != null){
            count++;
            temp = temp.next;
        }

        int[] result = new int[count];  // 根据链表的节点个数来定义新建数组的长度
        // 重点思路：从右往左遍历k--
        int k = count - 1;
        while(head != null){
            result[k--] = head.val;
            head = head.next;
        }

        return result;

    }
}

0 赞同 0 条回复

遇事不决睡大觉普通 2024年11月24日上午12:07

“`java
class Solution {
public int[] reverseBookList(ListNode head) {
Stack stack = new Stack<>();
ListNode p = head;
while (p != null) {
stack.push(p.val);
p = p.next;
}
int[] ans = new int[stack.size()];
int index = 0;
while (!stack.isEmpty()) {
ans[index++] = stack.pop();
}
return ans;
}
}
//倒着来就行

0 赞同 0 条回复

登录以回复

岱永久会员 2024年11月23日下午8:59

遍历反向存数组

class Solution {
    public int[] reverseBookList(ListNode head) {
        int l = 0;
        ListNode p = head;
        while(p!=null){
            l++;
            p = p.next;
        }
        int[] t = new int[l];
        p = head;
        for(int i = l-1 ; i >=0 ; i-- ){
            t[i] = p.val;
            p = p.next;
        }
        return t;


    }
}

0 赞同 1 条回复

岱永久会员 @ 岱 2024年11月23日下午8:59

class Solution {
    ArrayList<Integer> t = new ArrayList<Integer>();
    public int[] reverseBookList(ListNode head) {
        recur(head);
        int[] ans = new int[t.size()];
        for(int i = 0; i < ans.length; i++)
            ans[i] = t.get(i);
        return ans;
    }

    private void recur(ListNode p){
        if(p == null)return;
        recur(p.next);
        t.add(p.val);
    }
}

🍊 普通 2024年11月23日下午6:11
直接翻转链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseNodeList(ListNode head){
if(head null || head.next null) return head;
ListNode p = head, q = p.next;
while(q.next != null){
p = p.next;
q = q.next;
}
p.next = null;
q.next = reverseNodeList(head);
return q;
}
```
public int[] reverseBookList(ListNode head) {
    head = reverseNodeList(head);
    List<Integer> res = new ArrayList<>();
    ListNode p = head;
    while(p != null){
        res.add(p.val);
        p = p.next;
    }
    int[] r = new int[res.size()];
    for(int i = 0; i < res.size(); i++) r[i] = res.get(i);
    return r;
}
```
}
0 赞同 0 条回复

登录以回复
biangbb 普通 2024年11月23日上午11:13

class Solution {
public int[] reverseBookList(ListNode head) {
int arr[]=new int[10000];
int len=0;
while(head!=null){
arr[len]=head.val;
head=head.next;
len++;
}
int n=len–;
for(int i=0;i<len;i++,len–){
int temp=arr[i];
arr[i]=arr[len];
arr[len]=temp;
}
int result[]=new int[n];
for(int i=0;i<n;i++){
result[i]=arr[i];
}
return result;
}
}//中文

0 赞同 0 条回复

登录以回复
越努力越幸运普通 2024年11月22日下午11:46

“`c++
class Solution {
public:
vector reverseBookList(ListNode* head) {
if(!head)
{
return {};
}
int count = 0;
ListNode* temp = head;
while(temp)
{
count++;
temp = temp->next;
}
vector res(count);
int k = count – 1;
while(head)
{
res[k–] = head->val;
head = head->next;
}
return res;
}
};
“`
//从右往左

0 赞同 0 条回复

登录以回复
Kisara 普通 2024年11月22日下午8:25
“java代码

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
int[] res;
int i=0;
int j=0;
public int[] reverseBookList(ListNode head) {
if(headnull) return new int[0];
solve(head);
return res;
}
```
void solve(ListNode head){
    if(head==null) {
        res=new int[i];
        return;
    }

    i++;
    solve(head.next);
    res[j]=head.val;
    j++;
}
```
}

O（N） O
0 赞同 0 条回复

登录以回复

Poetry and distance 永久会员 2024年11月22日下午8:16

思路：为空的链表打印为空，统计链表长度，定义数组，从前往后遍历，从后往前向数组中增加值
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] reverseBookList(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];
        temp=head;
        int k=count-1;
        while(temp!=null){
            res[k--]=temp.val;
            temp=temp.next;
        }
        return res;
    }
}
时间复杂度：O(n)
空间复杂度:O(n)

0 赞同 0 条回复

Pendulumpal 普通 2024年11月22日下午5:42

复杂度 T O(n), M O(n)

“`c++
vectorans;
void dfs(ListNode* head){
if(head==nullptr)return;
dfs(head->next);
ans.push_back(head->val);
return;
}
vector reverseBookList(ListNode* head) {
dfs(head);
return ans;
}
“`

0 赞同 0 条回复

登录以回复
黑键〰普通 2024年11月22日下午3:53

/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val=undefined ? 0 : val)
* this.next = (next=undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {number[]}
*/
var reverseBookList = function(head) {
if(head = null) return []
let p0 = head
let res = []
while(p0 ! null) {
res.unshift(p0.val)
p0 = p0.next
}
return res
};

思路：看了下帅地视频的讲解，感觉有种大脑突然开窍的感觉，打破惯性思维从右往左遍历，角度好好，虽然自己写出来的还是这种很普通的
时间空间复杂度：都是O(N)

0 赞同 0 条回复

登录以回复

Rad 普通 2024年11月22日下午2:26

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] reverseBookList(ListNode head) {
        if (head == null) return new int[0];
        int count = 0;
        ListNode temp = head;
        while(temp != null)
        {
            count ++;
            temp = temp.next;
        }
        int k = count - 1;
        int[] res = new int[count];
        while(head != null)
        {
            res[k--] = head.val;
            head = head.next;
        }
        return res;


    }
}

时间On
空间O1

0 赞同 0 条回复

zing 普通 2024年11月22日上午11:26

这就是递归吗

class Solution:
    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
        temp = head
        cnt = 0
        while temp:
            temp = temp.next
            cnt += 1

        ans = [0]*cnt
        i = -1
        while head:
            ans[i] = head.val
            head = head.next
            i -= 1

        return ans

0 赞同 0 条回复

Firefly 普通 2024年11月22日上午8:52

/**
* 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 reverseBookList(ListNode head) {
int nCount=0;
vector res;
for(auto p=head;p!=nullptr;p=p->next)
{
nCount++;
}
res.resize(nCount);
for(auto p=head;p!=nullptr;p=p->next)
{
res[nCount-1]=p->val;
nCount–;
}
return res;
}
};
使用Vector

0 赞同 0 条回复

登录以回复
youngsir 普通 2024年11月22日上午8:29

打卡
/**
* 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 res;
vector reverseBookList(ListNode head) {
find(head);
return res;
}
void find(ListNode* head){
if(head nullptr){
return;
}
find(head->next);
res.push_back(head->val);
}
};

0 赞同 0 条回复

登录以回复

jaron 普通 2024年11月22日上午7:57

时间复杂度：O(n)
额外空间复杂度：O(1)

class Solution {
    public int[] reverseBookList(ListNode head) {
        if (head == null) return new int[0];
        ListNode temp = head;
        // 统计链表个数
        int cnt = 0;
        while (temp != null) {
            cnt++;
            temp = temp.next;
        }
        int[] arr = new int[cnt];
        int k = cnt - 1;
        // 反向添加
        while (head != null) {
            arr[k--] = head.val;
            head = head.next;
        }
        return arr;
    }
}

0 赞同 0 条回复

Tom Yuan 普通 2024年11月22日上午2:45

方法1：stack 正向push进一个其他list 然后将其反向pop

class Solution:
    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
        stack = []
        temp = head

        while temp != None:
            stack.append(temp.val)
            temp = temp.next

        result = []
        for i in range(len(stack)):
            result.append(stack.pop())

        return result

time: O(n)
space: O(n)

方法2：正向走一遍源链表获取长度然后再走一遍链表并反向塞入结果数组
这两种方法都是要遍历两遍。

class Solution:
    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
        count = 0
        temp = head

        # count the length of the list
        while temp is not None:
            count += 1
            temp = temp.next

        result = [0] * count
        temp = head
        # fill the list in reverse
        for i in range(count):
            result[count - i - 1] = temp.val
            temp = temp.next

        return result

中间的for也可以用while 我觉得用for可以搞定index的问题就用了实际上得别忘了-1因为index是0开始。
time O(n) space O(n)

方法3：递归借用了lc评论区的解法本质也是利用了递归隐含了栈的特性，最后会从链表最后开始累计结果list。

class Solution:
    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
        return self.reverseBookList(head.next) + [head.val] if head else []
# 作者：Krahets
# 链接：https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/solutions/97270/mian-shi-ti-06-cong-wei-dao-tou-da-yin-lian-biao-d/

不得不说这个写法还是很鸡贼的一遍出可能目前还有点难度还是朴实的写stack或者反向填充好点。

0 赞同 0 条回复

mpweixin用户普通 2024年11月22日上午12:21

class Solution {
public:
vector reverseBookList(ListNode* head) {
vector result;
stack l;
while(head){
l.push(head->val);
head = head->next;
}
while(!l.empty()){
result.push_back(l.top());
l.pop();
}
return result;
}
};
思路：结果是倒序输出，正向读链表，并依次入栈，出栈顺序即为结果。
时间复杂度O(n)，空间复杂度O(n)。

0 赞同 0 条回复

登录以回复

咕普通 2024年11月21日下午11:56

class Solution:
    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
        if head == None:
            return []

        count = 0
        temp = head
        while temp != None:
            count += 1
            temp = temp.next

        res = [0] * count
        while count != 0:
            res[count -len(res) -1] = head.val
            head = head.next
            count -= 1
        return res

时间O(n) 空间O(n)

0 赞同 0 条回复

Xiang. 永久会员 2024年11月21日下午11:30

class Solution {
public int[] reverseBookList(ListNode head) {
List tmp=new ArrayList<>();
reverse(head,tmp);
int len=tmp.size();
int[] arr=new int[len];
for(int i=0;i<len;i++){
arr[i]=tmp.get(i);
}
return arr;
}
void reverse(ListNode head,List list){
if(headnull) return;
reverse(head.next,list);
list.add(head.val);
}
}

时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

登录以回复

. 普通 2024年11月21日下午10:51

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] reverseBookList(ListNode head) {
        int cnt = 0;
        ListNode tmp = head;
        if(head == null){
            return new int[0];
        }

        while(tmp != null){
            cnt++;
            tmp = tmp.next;
        }
        int[] num = new int[cnt];
        for(int i = cnt-1; i>=0;i--){
            num[i] = head.val;
            head = head.next;
        }
        return num;
    }
}

时间O(n),空间O(1)

0 赞同 0 条回复

momo 普通 2024年11月21日下午10:36

class Solution:
def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
ans = []
while(head):
ans.append(head.val)
head = head.next
ans = ans[::-1]
return ans
时间复杂度O(n) 空间复杂度O(n)

0 赞同 0 条回复

登录以回复

生活在经验里普通 2024年11月21日下午10:31

func reverseBookList(head *ListNode) []int {
    if head == nil {
        return nil
    }
    return append(reverseBookList(head.Next), head.Val)
}
递归到结束条件，倒序插入元素值到切片中

0 赞同 0 条回复

晓宇普通 2024年11月21日下午10:30

vector reverseBookList(ListNode* head) {
if(head nullptr) return {};
ListNode *p = head, *q = head;
int cnt = 0;
while(p){
p = p->next;
cnt++;
}
vector v(cnt);
while(q){
v[–cnt] = q->val;
q = q->next;
}
return v;
}
时间复杂度 o(n), 空间复杂度o(n)

0 赞同 0 条回复

登录以回复

张君雅小妹妹普通 2024年11月21日下午10:18

  public int[] reverseBookList(ListNode head) {
        if(head == null) return new int[0];
        ListNode cur = head;
        int cnt = 0;
        while(cur != null){
            cnt++;
            cur = cur.next;
        }
        cur = head;
        int i = cnt - 1;
        int[] res = new int[cnt];
        while(cur != null){
            res[i--] = cur.val;
            cur = cur.next;
        }
        return res;
    }

时间复杂度O(n)，空间复杂度O(1)

0 赞同 0 条回复

Renasc 普通 2024年11月21日下午10:02

时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public int[] reverseBookList(ListNode head) {
        if (head == null) {
            return new int[0];
        }

        // 定义临时节点
        ListNode curr = head;

        // 计算数组的大小
        int count = 0;
        while (curr != null) {
            count++;
            curr = curr.next;
        }

        // 定义数组
        int[] res = new int[count];

        // 给数组赋值
        ListNode temp = head;
        int k = count - 1;
        while (temp != null) {
            res[k] = temp.val;
            k--;
            temp = temp.next;
        }
        return res;        
    }
}

0 赞同 0 条回复

parsons 普通 2024年11月21日下午9:12

1.遍历数组直到链表末尾
2.递归倒序返回，将链表数据添加到数组中
3.返回数组
class Solution {
public:
vector ans;
vector reverseBookList(ListNode* head) {
reverse(head);
return ans;
}
void reverse(ListNode* head){
if(!head) return;
reverse(head->next);
ans.push_back(head->val);
}
};
时间o(n)
空间o(n)

0 赞同 0 条回复

登录以回复

Jerry 普通 2024年11月21日下午8:33

时间o(n)
空间o(1)

class Solution {
public:
    vector<int> ans;
    vector<int> reverseBookList(ListNode* head) {
        reverse(head);
        return ans;
    }
    void reverse(ListNode* head){
        if(!head) return;
        reverse(head->next);
        ans.push_back(head->val);
    }
};

0 赞同 0 条回复

月下足迹普通 2024年11月21日下午8:33
//遍历链表，然后用头插法，最后得到的链表是和原来相反的，然后再遍历链表，时间复杂度为O(N),空间为O(1)

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public int[] reverseBookList(ListNode head) {
int nums = 0;
if(head null) {
int [] arr = new int [0];
return arr;
}
ListNode p1 = new ListNode(-1);
ListNode cur = head;
ListNode nextListNode = head;
//头插法倒序
while (cur != null) {
nextListNode = cur.next;
cur.next = p1.next;
p1.next = cur;
cur = nextListNode;
nums++;
}
```
    int [] arr = new int [nums];
    //遍历链表

    for (int i = 0; i < arr.length; i++) {
        arr[i] = p1.next.val;
        p1 = p1.next;
    }
    return arr;
}
```
}
0 赞同 0 条回复

登录以回复

mpweixin用户普通 2024年11月21日下午8:22

a.思路讲解
1.将链表元素值放进容器中
2.将容器逆序打印
b.代码

class Solution {
public:
    vector<int> reverseBookList(ListNode* head) {
        vector<int> res;
        if(!head) return res;
        while(head)
        {
            res.push_back(head->val);
            head = head->next;
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

c.时间复杂度o(n)，n为链表长度；空间复杂度o(n)，使用了额外的容器数组；

0 赞同 0 条回复

lQl 永久会员 2024年11月21日下午8:19

递归:

class Solution {
    Queue<Integer> Book = new LinkedList();
    public int[] reverseBookList(ListNode head) {
        reverseList(head);
        int size = Book.size();
        int[] re = new int[size];
        for(int i = 0;i<size;i++){
            re[i] = Book.poll();
        }
        return re;
    }
    public void reverseList(ListNode head) {
        if(head==null){
            return;
        }
        reverseList(head.next);
        Book.add(head.val);
    }
}

0 赞同 0 条回复

🌟 普通 2024年11月21日下午8:17

栈时间 O n 空间On
class Solution {
public:
vector reverseBookList(ListNode* head) {

    stack<int> s;
    while(head!=nullptr){
        s.push(head->val);
        head=head->next;
    }
    vector <int> v;
    while(s.size()){
        v.push_back(s.top());
        s.pop();
    }
    return v;
}

};

递归
class Solution {
public:

vector<int> reverseBookList(ListNode* head) {


    if(head==nullptr) return {};
    vector<int> v;
    if(head->next!=nullptr) v=reverseBookList(head->next);
    v.push_back(head->val);
    return v;

}

};

0 赞同 0 条回复

WYX 普通 2024年11月21日下午8:10

思路：使用栈结构

class Solution {
    public int[] reverseBookList(ListNode head) {
        Stack<Integer> stack =  new Stack<>();

        while(head != null){
            stack.push(head.val);
            head = head.next;
        }

        int[] ans = new int[stack.size()];

        int i = 0;
        while(!stack.isEmpty()){
            ans[i] = stack.pop();
            i ++;
        }

        return ans;

    }
}

0 赞同 0 条回复

苯庸普通 2024年11月21日下午8:10
class Solution {
List res = new ArrayList();
public int[] reverseBookList(ListNode head) {
dfs(head);
int[] ans = new int[res.size()];
for(int i = 0; i < ans.length; i++){
ans[i] = res.get(i);
}
return ans;
}
```
void dfs(ListNode cur){
    if(cur == null){
        return;
    }
    dfs(cur.next);
    res.add(cur.val);
}
```
}
思路：递归直到为空再依次返回记录节点值，从而获取到倒序值
时间：O（n）
空间：O（n）
0 赞同 0 条回复

登录以回复
迢迢星野普通 2024年11月21日下午7:41
```
class Solution {
    public int[] reverseBookList(ListNode head) {
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        int[] res = new int[len];
        cur = head;

        for (int i = len - 1; i >= 0; i--) {
            res[i] = cur.val;
            cur = cur.next;
        }
        return res;
    }
}
```
遍历链表，记录链表的长度，创建结果数组 res。再次遍历数组，倒序填充元素到数组即可。

也可以第一遍遍历链表时，使用集合用来存储链表节点的值，再倒序填充结果数组即可。

时间复杂度：O(n)，遍历了两边链表
空间复杂度：O(n)，需要一个大小为 n 的数组用来存储链表节点的值。
2 赞同 0 条回复

登录以回复

# 回答此问题取消回复

后才能回答