晚睡晚起起不来永久会员 2024年3月29日下午6:15

初始化temp和count
利用temp进行遍历查看最开始的head有多少个元素，用count计数
获取到count的值也就是head的个数后，创建res数组，大小为count
while遍历head
k=count-1 也就是最后一个位置
把head每一个值，放入res中，位置是k 每一次遍历从后往前就是k–
每一次遍历head都要往后移动，直到尾部null退出循环

java
class Solution {
    public int[] reverseBookList(ListNode head) {
//判断特殊情况，非空输入返回空的数组
      if(head ==null) return new int[0];
//初始化temp指向head
      ListNode temp = head;
      int count = 0;
//进行遍历，查看一共有多少个元素在head中
      while(temp!=null){
        count++;
        temp = temp.next;
      }
//创建新的数组，空间大小是刚才遍历的count值
      int[] res = new int[count];
      int k = count-1;
//head的值给新的数组，从最后面给，就是k，每回往前移动就是k--,把值依次填入
      while(head!=null){
        res[k--] = head.val;
//最后head继续往前
        head = head.next;
      }

      return res;

    }
}

0 赞同 0 条回复

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

”’python
def reverseBookList(self, head):
“””
:type head: Optional[ListNode]
:rtype: List[int]
“””
#用递归，分解为子问题：头节点+反转子列表
if head is None:
return []
return self.reverseBookList(head.next) + [head.val]
时间复杂度O(n),空间复杂度O(n)
解释：时间复杂度：假设链表长度为 n，对于每个节点都会进行递归操作，因此时间复杂度可以表示为 O(n)，即与链表长度成正比。
空间复杂度：在递归过程中，需要维护递归调用栈，其空间复杂度取决于递归的深度。在最坏情况下，递归深度等于链表长度 n，因此空间复杂度为 O(n)。此外，还需要额外的空间来存储每个节点值构成的列表，列表的长度也为 n，因此额外空间复杂度也为 O(n)。

0 赞同 0 条回复

June 普通 2024年3月19日下午4:02

//反转链表
class Solution {
public int[] reverseBookList(ListNode head) {
if (head null) {
return new int[0];
}
int num = 0;
ListNode temp = head;
while (temp != null) {
temp = temp.next;
num++;
}
int[] returnInt = new int[num];
int index = num-1;
while (head != null) {
returnInt[index] = head.val;
index–;
head = head.next;
}
return returnInt;
}
}

0 赞同 0 条回复

山月普通 2024年3月14日下午12:27

/**
* 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) {}
* };
*/
#include

class Solution {
public:
vector reverseBookList(ListNode* head)
{
vector result;
if(head nullptr) return result;
int count = 0;
ListNode* cur = head;
while(cur != nullptr)
{
count++;
cur = cur->next;
}
cur = head;
vector resul(count);
int k = count-1;
while(cur != nullptr)
{
resul[k–] = cur->val;
cur = cur->next;
}
return resul;

};
//有很多种解法，目前只了解了一种，用数组的方式进行解决，后面再研究别的解法

0 赞同 0 条回复

RunAsOne 普通 2024年3月11日下午4:22

第四次打卡

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

0 赞同 0 条回复

雨落星空普通 2024年3月10日上午9:26

时间复杂度：O(n) 空间复杂度：O(1)
”’python
class Solution(object):
def reversePrint(self, head):
“””
:type head: ListNode
:rtype: List[int]
“””
if not head:
return []

    # 统计链表节点个数，方便创建数组
    count = 0
    temp = head
    while temp:
        count += 1
        temp = temp.next

    res = [0] * count
    k = count - 1
    # 从右往左填充数组
    while head:
        res[k] = head.val
        k -= 1
        head = head.next

    return res

0 赞同 0 条回复

mpweixin用户普通 2024年3月7日上午9:28

时间复杂度O(N),空间复杂度O(1)
class Solution {
public:
vectorv;
vector reverseBookList(ListNode* head) {
if(headnullptr)
return v;
if(head->nextnullptr){
v.push_back(head->val);
return v;
}
reverseBookList(head->next);
v.push_back(head->val);
return v;
}
};

0 赞同 0 条回复

e=mc² 普通 2024年3月6日下午4:08

class Solution {
    public int[] reverseBookList(ListNode head) {
        if (head == null) {
            return null;
        }
        int size = 0;
        ListNode temp = head;
        while (temp != null) {

            temp = temp.next;
            size++;
        }
        int[] result = new int[size];
        int k = size - 1;
        while (head != null) {
            result[k] = head.val;
            k--;
            head = head.next;
        }
        return result;
    }
}

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

0 赞同 0 条回复

C C 普通 2024年3月5日下午6:42

# 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 []

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

        res = [0] * count
        k = count - 1
        # 从右往左填充数组
        while head:
            res[k] = head.val
            k -= 1
            head = head.next
        return res

0 赞同 0 条回复

LAVI 普通 2024年3月5日下午3:44

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];
int index = count – 1;
while (head != null) {
res[index–] = head.val;
head = head.next;
}
return res;
}
}
时间复杂度O(n)
先计算出链表长度，再创建该长度的数组，再从尾到头插入链表数据

0 赞同 0 条回复

YOLO 普通 2024年3月5日下午12:32

“`C++
//输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
class Solution {
public:
vector reverseBookList(ListNode* head) {
if(head == nullptr){
return {};
}
int len = 0;
ListNode *temp = head;
while(temp != nullptr){
len++;
temp = temp->next;
}
vector res(len);
int k=len-1;
while(head != nullptr){
res[k] = head->val;
head = head->next;
k–;
}
return res;
}
};
“`

0 赞同 0 条回复

莫～慢～待普通 2024年3月4日下午11:50

class Solution {
int[] res;
public int[] reverseBookList(ListNode head) {
int count=0;
ListNode pre=null;
while(head!=null)
{
count++;
ListNode temp=head.next;
head.next=pre;
pre=head;
head=temp;
}
res=new int[count];
int i=0;
while(pre!=null)
{
res[i]=pre.val;
i++;
pre=pre.next;
}
return res;
}
}
第一次反转链表记录长度，第二次直接遍历给数组赋值

0 赞同 0 条回复

繁星普通 2024年3月4日下午11:03

方法一：递归，时间复杂度O(n)，空间复杂度O(n)
class Solution {
List list = new ArrayList<>();
public int[] reverseBookList(ListNode head) {
recursion(head);
int[] arr = new int[list.size()];
for(int i = 0; i < arr.length; i++) {
arr[i] = list.get(i);
}
return arr;
}
public void recursion(ListNode cur) {
if(cur null) {
return;
}
reverseBookList(cur.next);
list.add(cur.val);
}
}
方法二：栈，时间复杂度O(n)，空间复杂度O(n)
class Solution {
List list = new ArrayList<>();
public int[] reverseBookList(ListNode head) {
Stack stack = new Stack<>();
while(head != null) {
stack.add(head.val);
head = head.next;
}
int[] arr = new int[stack.size()];
int i = 0;
while(!stack.isEmpty()) {
arr[i] = stack.pop();
i++;
}
return arr;
}
}

0 赞同 0 条回复

30tcq 普通 2024年3月4日下午5:57

思路：第一遍遍历计算链表长度，第二遍遍历计算数值

“`c++
/**
* 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) {
if(head == NULL) return {}; //返回为空的数组
ListNode* tmp;
tmp = head;

    int cnt = 0;
    while(tmp){
        cnt++;
        tmp = tmp->next;
    }

vector<int> rs(cnt);       //声明一个长度为cnt的数组
int i = cnt - 1;
while(head){
    rs[i] = head->val;
    head = head->next;
    i--;
}
return rs;

}


};
“`

时间复杂度O（n）

空间复杂度O（n）

0 赞同 0 条回复

mpweixin用户普通 2024年3月4日下午5:22

public int[] reverseBookList(ListNode head) {
List list =new ArrayList<>();
while(head!=null){
list.add(head.val);
head=head.next;
}
int n=list.size();
int[] ans =new int[n];
for(int i=0;i<n;i++) ans[i]=list.get(n-1-i);
return ans;
}
思路：把数据存在数组中倒序访问数组双O(n)
没注意审题以为要用尾插法重新构造链表

0 赞同 0 条回复

Yeah~ 普通 2024年3月4日下午5:07

/**
* 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 ret;
vector reverseBookList(ListNode head) {
if(head nullptr) return {};
if(head->next != nullptr)
reverseBookList(head->next);
ret.push_back(head->val);
return ret;
}
};
这里用的递归，也可用栈实现。
时间空间复杂度都是O(n)

0 赞同 0 条回复

湘江小水鬼普通 2024年3月4日下午4:27

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode next;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int reverseBookList(struct ListNode* head, int* returnSize) {
struct ListNodep=head;
int cnt=0;
while(p){ //遍历链表得到链表结点数量
cnt++;
p=p->next;
}
*returnSize=cnt;
int ans=(int)malloc(cntsizeof(int));
int i=cnt-1;
p=head;
while(p){
ans[i–]=p->val; //倒序将链表元素放入数组
p=p->next;
}
return ans;
}打卡

0 赞同 0 条回复

阿野普通 2024年3月4日下午3:56

#打卡
#栈
var reverseBookList = function(head) {
let arr = [];
let node = head;
while(node){
arr.unshift(node.val);
node = node.next;
}
return arr;
};
#递归
var reverseBookList = function(head) {
if(!head) return []
let result = reverseBookList(head.next)
result.push(head.val);
return result;
};

0 赞同 0 条回复

小耿普通 2024年3月4日下午3:55

“`C++
class Solution {
public:
vector reverseBookList(ListNode* head) {
if (!head) return vector();

    vector<int> result;
    reverse_list(head, result);
    return result;
}

void reverse_list(ListNode* head, vector<int>& temp) {
    if(head->next) {
        reverse_list(head->next, temp);
    } 
    // 这里不能加else
    temp.push_back(head->val);

}

};

“`

0 赞同 0 条回复

kfaebot 普通 2024年3月4日下午2:20

/**
 * 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> reverseBookList(ListNode* head) {
        //先输入到栈里
        stack<int>books;
        while(head!=nullptr){
            books.push(head->val);
            head=head->next;
        }

        //再输出到向量得到结果
        vector<int>booklist;
        while(!books.empty()){
            booklist.push_back(books.top());
            books.pop();
        }
        return booklist;
    }
};
\\时间复杂度O(N)
\\空间复杂度O(N)

0 赞同 0 条回复

Jankin 普通 2024年3月4日下午12: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) {
        if (head == null)
            return new int[0];
        int size = 0;
        ListNode temp = head;
        while (temp != null) {
            size++;
            temp = temp.next;
        }
        int[] res = new int[size];
        while (head != null) {
            res[--size] = head.val;
            head = head.next;
        }
        return res;
    }
}

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

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月4日上午11:25

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

class Solution {
public:
    // 递归到链表尾，然后回溯的时候将节点加入到res中
    void _reverse(ListNode* head, vector<int>& res) {
        if(!head) return;
        _reverse(head->next, res);
        res.emplace_back(head->val);
    }
    vector<int> reverseBookList(ListNode* head) {
        if(!head) return {};
        vector<int> res;
        _reverse(head, res);
        return res;
    }
};

0 赞同 0 条回复

一个达不刘普通 2024年3月4日上午10:13

思路：
从头开始遍历链表，存到数组容器当中，（类似栈的原理，先进后出）。输出数组，即逆序输出单链表。

遍历链表，存数组时候使用了递归，

class Solution {
public:
vector reverseBookList(ListNode* head) {
recur(head);
return res;
}
private:
vector res;
void recur(ListNode *head){
if(head nullptr) return;
recur(head->next);
res.push_back(head->val);
}
};

0 赞同 0 条回复

=.= 普通 2024年3月3日下午11:24

/**
* 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 n = 0;
    ListNode p = head;
    while(p != null){
        n++;
        p = p.next;
    }   
    int[] ans = new int[n];
    n--;
    p=head;
    while(p != null){
        ans[n--] = p.val;
        p = p.next;
    }

    return ans;
}

}

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

0 赞同 0 条回复

晚风、普通 2024年3月3日下午11:00

使用递归方法：
递推+回溯
class Solution:
def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
if head:
return self.reverseBookList(head.next) + [head.val]
else:
return []
node为空的时候为递推的终止，回溯的起点
其余时候将当前的val的+到最后
时间复杂度：o(N)
空间复杂度：o(N)

0 赞同 0 条回复

mpweixin用户普通 2024年3月3日下午9:59

java
class Solution{
ArrayList tmp = new ArrayList();
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年3月3日下午9:54

先反转再输出
/**
* 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 count = 0;
ListNode temp = head;
while(temp != null){
count++;
temp = temp.next;
}
int[] ans = new int[count];

    ListNode pre = null,cur = head;
    while(cur != null){
        ListNode ne = cur.next;
        cur.next = pre;
        pre = cur;
        cur = ne;
    }
    int a = 0;
    while(pre != null){
        ans[a++]= pre.val;
        pre = pre.next;
    }
    return ans;
}

}

0 赞同 0 条回复

Free 普通 2024年3月3日下午8:13

/**
 * 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 
{
    vector<int> res;
public:
    vector<int> reverseBookList(ListNode* head)
    {
        func(head);
        return res;
    }

    void func(ListNode* node)
    {
        if(node == nullptr)
            return;
        func(node->next);
        res.push_back(node->val);
    }
};

时空复杂度o(n)

0 赞同 0 条回复

一颗红豆普通 2024年3月3日下午5:22

时间复杂度o（n）空间复杂度o（n）
将链表进行遍历，反向放入数组即可需提前获取链表长度以开辟等大的数组
/**
* 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) {
if(headnullptr)
{
return {};
}
ListNode *temp = head;
int count = 0;
while(temp!=nullptr)
{
count ++;
temp = temp->next;
}
vector a(count);
int k = count-1;
while(head!=nullptr)
{
a[k–] = head->val;
head = head->next;
}
return a;

};

0 赞同 0 条回复

Monou 普通 2024年3月3日下午5:20

直接数组
/**
* 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) {
ListNode node = head;
int len = 0;
while(node != null){
node = node.next;
len++;
}
int[] ans = new int[len–];
while(head != null){
ans[len–] = head.val;
head = head.next;
}
return ans;

}

0 赞同 0 条回复

一期一会普通 2024年3月3日下午4:32

使用栈存储链表，输出到数组中
时间复杂度为O(N),空间复杂度为O(N),

 * 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> reverseBookList(ListNode* head) {
        stack<int>temp;
        while(head != nullptr)
        {
            temp.push(head->val);
            head = head->next;
        }
        vector<int>res;
        while(!temp.empty())
        {
            res.push_back(temp.top());
            temp.pop();
        }
        return res;
    }
};

0 赞同 0 条回复

　南木普通 2024年3月3日下午4:23

时间复杂度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 {

     ArrayList<Integer> arr = new ArrayList<Integer>();
    public int[] reverseBookList(ListNode head) {
        recur(head);
        //将ArrayList转化为int[]
        int[] intArray = arr.stream().mapToInt(Integer::intValue).toArray();
        return intArray;
    }

    public void recur(ListNode node) {
        if (node == null)
            return;
        recur(node.next);
        arr.add(node.val);

    }
}

0 赞同 0 条回复

Laboratory 普通 2024年3月3日下午2:46

/**
 * 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> list = new ArrayList<>();
    public int[] reverseBookList(ListNode head) {
        reverse(head);
        int[] res = new int[list.size()];
        for(int i = 0; i< list.size() ;i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void reverse(ListNode head) {
        if(head == null) {
            return;
        }
        reverse(head.next);
        list.add(head.val);
    }
}

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

0 赞同 0 条回复

lucky耶耶耶*👻*～普通 2024年3月3日下午2:18

public class Solution {
    public int[] printListFromTailToHead(ListNode head) {
        //非空判断
        if (head == null) {
            return new int[0];
        }
        ListNode temp = head;
        //计算节点数量
        int count = 0;
        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 条回复

普通 2024年3月3日下午1:36

class Solution {
public:
vector reverseBookList(ListNode* head) {
if(headnullptr) return vector();
int count=0;
ListNode *p=head;
while(p!=nullptr)
{
count++;
p=p->next;
}
vector result(count);
p=head;
for(int i=count-1; i >= 0; i–)
{
result[i] = p->val;
p = p->next;
}
return result;
}
};
打卡
时间复杂度O(n),空间复杂度O(1)

0 赞同 0 条回复

墨丘俐普通 2024年3月3日下午12:41

/**
* 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 len = 0;
ListNode temp = head;
while(temp!=null){
len++;
temp = temp.next;
}
int [] res = new int[len];
for(int i =len-1;i>=0;i–){
res[i] = head.val;
head = head.next;

    }
    return res;

}

}

0 赞同 0 条回复

神经蛙普通 2024年3月3日下午12:00

int* reverseBookList(struct ListNode* head, int* returnSize){
struct ListNode *temp = head;
int count = 0;
while(temp){
count++;
temp = temp->next;
}
*returnSize = count;
int *array = malloc(count * sizeof(int));
int k = count -1;
temp = head;
while(temp)
{
array[k–] = temp->val;
temp = temp->next;
}
return array;
}
思路：从右向左遍历
时间复杂度：O（n）；空间复杂度O（N）

0 赞同 0 条回复

ChenZhangHangTime 永久会员 2024年3月3日上午10:59

// 从右边=往左填充
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;
}

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月3日上午10:52

class Solution {
    public int[] reverseBookList(ListNode head) {
        // 空链表
        if(head==null) return new int[0];

        //只有一个结点
        if(head.next==null){
            int num[] = new int[1];
            num[0]=head.val;
            return num;  
        }

        int len=1;
        ListNode p=head;
        ListNode r=head.next;
        ListNode q;
        p.next=null;
        while(r!=null){
            q=r.next;
            r.next=p;
            p=r;
            r=q;
            len++;
        }

        int num[] = new int[len];
        for(int i=0;i<=len-1;i++){
            num[i]=p.val;
            p=p.next;
        }


        return num;
    }
}

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

0 赞同 0 条回复

Yuki 永久会员 2024年3月3日上午10:39

递归暂时不太理解
···
class Solution {
public:
vector reverseBookList(ListNode* head) {
stackst;
vectorres;
int tmp=0;
if(headnullptr)return res;
ListNode*cur=head;

    while(cur!=nullptr){
        st.push(cur->val);
        cur=cur->next;
    }
    while(!st.empty()){
        tmp=st.top();
        res.push_back(tmp);
        st.pop();
    }
    return res;
}

};

“`
空间复杂度:：O(N)
时间复杂度：O(N)

0 赞同 0 条回复

持之以恒:-) 普通 2024年3月3日上午10:35

递归方式实现链表倒序打印

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

/**
 * 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) {

        List<Integer> list = new ArrayList<>();
        reverseLinkedList(head, list);
        int[] array = list.stream().mapToInt(Integer :: valueOf).toArray();
        return array;
    }

    private void reverseLinkedList(ListNode head, List<Integer> list){
        if(head == null)
            return ;
        reverseLinkedList(head.next, list);
        list.add(head.val);
    }
}

0 赞同 0 条回复

方铎码农普通 2024年3月3日上午10:28

辅助栈法

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

class Solution {
    Deque<Integer> tmp = new ArrayDeque<>();
    public int[] reverseBookList(ListNode head) {
        recur(head);
        int[] res = new int[tmp.size()];
        for (int i = 0; i < res.length; i++){
            res[i] = tmp.pop();
        }
        return res;
    }

    private void recur(ListNode head){
        while(head != null){
            tmp.push(head.val);
            head = head.next;
        }
    }
}

递归法

时间复杂度同上，空间复杂度同上，我个人更喜欢递归

/**
 * 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;
    }

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

0 赞同 0 条回复

mpweixin用户普通 2024年3月3日上午9:19

/**
* 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) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
List arr = new ArrayList<>();
while (pre != null) {
arr.add(pre.val);
pre = pre.next;
}
int[] res = new int[arr.size()];
for (int i = 0; i < arr.size(); i++) {
res[i] = arr.get(i);
}
return res;
}
}
时间复杂度O(n)

0 赞同 0 条回复

😴 普通 2024年3月3日上午9:03

/**
* 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 tmp = new ArrayList();
public int[] reverseBookList(ListNode head) {
recur(head);
int[] res = new int[tmp.size()];
for(int i = 0;i < res.lengtn; i++){
res[i] = tmp.get(i);
}
return res;

}
void recur(ListNode head){
    if(head == null) return;
    recur(head.next);
    tmp.add(head.val);

}

}
使用递归思想，一步一步深入，将值存在一个新的数组里面，后面在进行输出。
时间复杂度O(n)
空间复杂度O(n)
不足之处：思想能接受，但代码写不出

0 赞同 0 条回复

Yox 普通 2024年3月3日上午5:42

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 head None:
return []
res = []
cur = head
def reverseList(cur:Optional[ListNode]):
if cur.next None:
res.append(cur.val)
else:
reverseList(cur.next)
res.append(cur.val)
reverseList(cur)
return res

时间o（N）需完整遍历一遍空间o（N）

0 赞同 0 条回复

HU 普通 2024年3月3日上午4:12

/**
 * 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 new Array(0);

    // 统计链表节点个数，方便创建数组
    let count = 0;
    let temp = head;
    while(temp != null) {
        count++;
        temp = temp.next;
    }
    let res = new Array(count);
    let k = count - 1;

    for(let i = k; i >= 0; i--) {
        res[i] = head.val;
        head = head.next;
    }

    return res;
};

0 赞同 0 条回复

Deckkker 普通 2024年3月2日下午11:55

# 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 []

        def reversePrint(head):
            if head is None:
                return []

            return reversePrint(head.next) + [head.val]

        return reversePrint(head)

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

0 赞同 0 条回复

叫不醒装睡的人普通 2024年3月2日下午11:01

class Solution {
    // 递归额外空间开销比较大
    // 采用从右到左填充数组的方式解决问题
    // 先将链表遍历一遍，获取到数组大小
    // 再次遍历链表，反向填充数组元素
    public int[] reverseBookList(ListNode head) {
        if (head == null) {
            return new int[0];
        }
        ListNode temp = head;
        int size = 0;
        while (temp != null) {
            temp = temp.next;
            size++;
        }
        int[] result = new int[size];
        int idx = size - 1;
        while (head != null) {
            result[idx--] = head.val;
            head = head.next;
        }
        return result;
    }
    // 时间复杂度为 O(n)
    // 需要对链表进行完整遍历
    // 空间复杂度为 O(1)
    // 几个局部变量对于额外空间的占用都是常数大小
}

0 赞同 0 条回复

Jimmy 普通 2024年3月2日下午10: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<int> reverseBookList(ListNode* head) {

        ListNode *cur = head;
        int size = 0;
        while(cur != nullptr){
            size++;
            cur = cur->next;
        }
        vector<int> res(size);
        cur = head;
        while(cur != nullptr){
            res[--size] = cur->val;
            cur = cur->next;
        }
        return res;
    }
};

0 赞同 0 条回复

云无深雁影普通 2024年3月2日下午10:20

/**
* 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 {
private ArrayList list = new ArrayList();
private void recu(ListNode head){
if(head.next != null)
recu(head.next);
list.add(head.val);
}

public int[] reverseBookList(ListNode head) {
    if(head == null)
        return new int[0];
    recu(head);
    int[] ans = new int[list.size()];
    for(int i = 0; i < list.size(); i++){
        ans[i] = list.get(i);
    }
   return ans;


}

}
时间复杂度On
空间复杂度On

0 赞同 0 条回复

机电皮怪永久会员 2024年3月2日下午10:18

时间复杂度o（n）
空间复杂度o（n）
#CPP

class Solution {
public:
    vector result;

    vector reverseBookList(ListNode* head) 
    {
        if ( head == nullptr )
        {
            return vector();
        }

        reverse(head);

        return result;
    }

    void reverse(ListNode* head)
    {
        if( head == nullptr )
        {
            return;
        }
        if( head->next == nullptr )
        {
            result.push_back(head->val);
            return;
        }
        reverse(head->next);

        result.push_back(head->val);
    }
};

0 赞同 0 条回复

NULL 普通 2024年3月2日下午10:13

class Solution {
ArrayList temp = new ArrayList();
public int[] reverseBookList(ListNode head) {
recur(head);
int[] res = new int[temp.size()];
for(int i = 0; i < res.length; i++){
res[i] = temp.get(i);
}
return res;
}
public void recur(ListNode head){
if(head null)return;//递归出口
recur(head.next);
temp.add(head.val);
}
}

0 赞同 0 条回复

Let it be 永久会员 2024年3月2日下午9:53

class Solution {
int[] res;
int a = 0;
int b = 0;
public int[] reverseBookList(ListNode head) {
recur(head);
return res;
}

public void recur(ListNode head){
    if(head == null){
        res = new int[a];
        return;
    }
    a++;
    recur(head.next);
    res[b] = head.val;
    b++;
}

}时间复杂度 O(N)空间复杂度O(N)

0 赞同 0 条回复

MARS 普通 2024年3月2日下午9:47

day2 第二道题
···TypeScript
function trainningPlan(head: ListNode | null): ListNode | null {
return reverse(null,head)

function reverse(prev:ListNode | null,head:ListNode |null){
    if(!head){
        return prev
    }
    let next = head.next
    head.next = prev
    prev = head
    return reverse(prev,next)
}

};
···

0 赞同 0 条回复

言之命至普通 2024年3月2日下午9:43

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;
    }
}

0 赞同 0 条回复

helloMoon 普通 2024年3月2日下午9:12

从尾到头打印链表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 {
    public int[] reverseBookList(ListNode head) {
        if(head == null)
            return new int[0];

        int cnt = 0;
        ListNode tmp = head;
        while(tmp != null){
            cnt ++ ;
            tmp = tmp.next;
        }

        int[] res = new int[cnt];
        int k = cnt - 1;

        while(head != null){
            res[k -- ] = head.val;
            head = head.next;
        }

        return res;
    }
}

0 赞同 0 条回复

Fancy 普通 2024年3月2日下午9:07

“`python
打卡
class Solution:
def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
if not head:
return []
# 递归
resList = []
cur = self.reverse(head, resList)
return resList

def reverse(self, cur, resList):
    if not cur.next:
        resList.append(cur.val)
        return cur
    self.reverse(cur.next, resList)
    resList.append(cur.val)
    return cur

0 赞同 0 条回复

Raphtalia. 普通 2024年3月2日下午8:21

/**
* 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) {
if(!head) return {};
ListNode* tmp = head;
int cnt = 0;
while(tmp){
tmp = tmp->next;
cnt++;
}
vector ans(cnt, 0);
for(int i = cnt – 1; i >= 0; i –){
ans[i] = head->val;
head = head->next;
}
return ans;
}
};
时间复杂度O（n），空间复杂度O（1）

0 赞同 0 条回复

王位詮釋普通 2024年3月2日下午8:18

“`java
class Solution {
List list = new ArrayList<>();
public int[] reverseBookList(ListNode head) {
reverseForVal(head);
int[] result = new int[list.size()];
for(int i=0;i

0 赞同 0 条回复

零普通 2024年3月2日下午8:12

思路：递归处理，每次先去处理next节点。复杂度O(n)
代码：

“`java
public int[] reverseBookList(ListNode head) {
List list = new ArrayList<>();
handler(head,list);
//return list.toArray();
int[] array = new int[list.size()];
for (int i=0; ivoid handler(ListNode node, List list) { if (null node) return; handler(node.next,list); list.add(node.val); }

0 赞同 0 条回复

heathhou 普通 2024年3月2日下午8:06

class Solution {
public:
    vector<int> reverseBookList(ListNode* head) {
        if(head == nullptr){
            return {};
        }

        stack<int> stk;
        while(head){
            stk.push(head->val);
            head = head->next;
        }

        vector<int> v;
        while(!stk.empty()){
            v.push_back(stk.top());
            stk.pop();
        }
        return v;
    }
};

使用递归时，提示内存溢出
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

进取普通 2024年3月2日下午7:40

用栈做时间复杂度O(n) 空间复杂度O(n)
递归时间复杂度O(n) 空间复杂度O(1)

0 赞同 0 条回复

是hua不是pua 普通 2024年3月2日下午7:19

“`java
class Solution {
public int[] reverseBookList(ListNode head) {
ListNode head1 = new ListNode();
int i = 0;
while(head != null){
ListNode next = head.next;
head.next = head1.next;
head1.next = head;
head = next;
i++;
}
int[] result = new int[i];
ListNode cur = head1.next;
i = 0;
while(cur != null){
result[i] = cur.val;
i++;
cur = cur.next;
}
return result;
}
}
“` 反转链表常用头插法

0 赞同 0 条回复

mpweixin用户普通 2024年3月2日下午7:08

先遍布链表，获取长度；创建数组，从数组尾部开始赋值

/**
 * 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 N = 0;
        ListNode root = head;
        while (root != null) {
            root = root.next;
            N++;
        }
        int[] arr = new int[N];
        root = head;
        for (int i = N - 1; i >= 0; i--) {
            arr[i] = root.val;
            root = root.next; 
        }
        return arr;
    }
}

0 赞同 0 条回复

紫芝普通 2024年3月2日下午5:55

时间复杂度：O(n)
空间复杂度：O(n)
思路：创建一个虚拟头节点prehead，然后依次将链表反转，当head=nullptr时即反转完链表，然后根据prehead依次获取链表的值，保存到结果集vector<int> res中。

“`C++
class Solution {
public:
vector reverseBookList(ListNode* head) {
vector res;
if (head == nullptr) return res;
ListNode *prehead = nullptr;
ListNode *cur = nullptr;
while (head != nullptr) {
cur = head->next;
head->next = prehead;
prehead = head;
head = cur;
}
while (prehead) {
res.push_back(prehead->val);
prehead = prehead->next;
}
return res;
}
};
“`

0 赞同 0 条回复

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

共以下 65 个回答

递归方式实现链表倒序打印

辅助栈法

递归法

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

# 回答此问题取消回复

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

共以下 65 个回答

递归方式实现链表倒序打印

辅助栈法

递归法

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

# 回答此问题 取消回复

# 回答此问题取消回复