【链表专题】剑指 Offer 06. 从尾到头打印链表-跟着帅地玩副业，开拓第二曲线PlayOffer

招舟子普通 2023年8月24日下午6:27

“`java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
ArrayList a = new ArrayList<>();
public int[] reversePrint(ListNode head) {
recur(head);
int[] res = new int[a.size()];
for(int i=0;ivoid recur(ListNode head){ if(head==null){ return ; } recur(head.next); a.add(head.val); }

}
递归和Java ArrayList

0 赞同 0 条回复

Old think of qi 永久会员 2023年7月20日下午9:29

时间复杂度O（N)
空间复杂度O（N)
class Solution {
List list = new ArrayList<>();
public int[] reversePrint(ListNode head) {
reverse(head);
int size = list.size();
int[] arr = new int[size];
for(int i = 0;i < size;i++){
arr[i] = list.get(i);
}
return arr;
}

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

}

0 赞同 0 条回复

mpweixin用户普通 2023年7月17日下午10:27

时间：O(n)
空间：O(1)
class Solution {
public int[] reversePrint(ListNode head) {
if(head null){
return new int[0];
}
int len = 0;
ListNode tmp = head;
while(tmp != null){
len++;
tmp = tmp.next;
}
int[] arr = new int[len];
for(int i = len-1 ; head != null ;i–){
arr[i] = head.val;
head = head.next;
}
return arr;

}

0 赞同 0 条回复

橙子陈普通 2023年7月15日下午6:12

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

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

        // 新建数组，从右至左存入链表值
        int[] res = new int[count];
        int len = count - 1;
        while (head != null) {
            res[len] = head.val;
            len--;
            head = head.next;
        }

        return res;
    }
}

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

0 赞同 0 条回复

ZJS 永久会员 2023年7月15日上午10:47

方法：递归
时间复杂度：O(n)
空间复杂度：O(n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    ArrayList<Integer> list = new ArrayList();

    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] res = new int[list.size()];

        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }

        return res;
    }

    // 将当前节点加入到列表list中
    public void recur(ListNode currNode){
        if(currNode == null){
            return;
        }

        // 在将当前节点加入到list中之前应先把下一节点加入
        recur(currNode.next);

        list.add(currNode.val);
    }
}

0 赞同 0 条回复

TT 永久会员 2023年7月8日下午10:47

class Solution {
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reversePrint(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 条回复

cute. 普通 2023年7月5日下午2:15

思路：原地反转，空间复杂度O(1),从右往左遍历

var reversePrint = 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;
    while ( head !== null ) {
        res[k--] = head.val;
        head = head.next;
    }
    return res;
};

0 赞同 0 条回复

与你同行普通 2023年7月3日上午11:36

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

/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reversePrint(head *ListNode) []int {
if head nil {
return []int{}
}
//1,3,2
subRes := reversePrint(head.Next)

//保存反转的值
subRes = append(subRes, head.Val)
//返回给subRes,这样值不会被重置
return subRes;

}

0 赞同 0 条回复

Gracelyne 普通 2023年7月1日下午3:48

时间：O(n)
空间：O(n): 递归将占用链表长度的栈空间
class Solution {
public:
    vector<int> res;
    vector<int> reversePrint(ListNode* head) {
        if(!head) return res;
        reversePrint(head->next);
        res.push_back(head->val);
        return res;
    }
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月1日下午12:50

先用递归进入到链表尾部，然后通过一个全局的ArrayList来进行数据的保存，最后将其转化为数组进行输出

class Solution {
    private static ArrayList<Integer> ans;//创建一个全局变量用来保存每个节点的信息
    public void getNum(ListNode head){//通过递归来从链表尾部开始访问
        if(head==null)return;
        getNum(head.next);//先进行深度遍历
        ans.add(head.val);//从尾节点开始奖每个节点的数据存入链表中
    }
    public int[] reversePrint(ListNode head) {
        ans=new ArrayList<>();//初始化
        getNum(head);//
        int[] arr=new int[ans.size()];//奖链表转化为数组输出
        for(int i=0;i<arr.length;i++){
            arr[i]=ans.get(i);
        }
        return arr;
    }
}

0 赞同 0 条回复

dys 普通 2023年6月29日下午2:51

public int[] reversePrint(ListNode head) {
if (head null) return new int[0];
ListNode a = head;
int length = 0;
while (head != null){
head = head.next;
length++;
}
int[] array = new int[length];
for(int i = length – 1; i >= 0; i–){
if (a != null){
array[i] = a.val;
a = a.next;
}
}
return array;
}

时间：O（n）需要遍历数组。空间：O（n）新建了数组和指针

0 赞同 0 条回复

Sexypig. 普通 2023年6月28日下午9:58

代码：

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        if not head:
            return []
        count=0
        cur=head
        while cur:
            count+=1
            cur=cur.next
        res=[0]*count
        while head:
            count-=1
            res[count]=head.val
            head=head.next
        return res

时间复杂度：遍历两次链表，用时为2*n，为O（n）
空间复杂度：O（1），未使用额外存储空间

0 赞同 0 条回复

淡色花樱普通 2023年6月28日下午7:44

““java
/**
* 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];
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(n)
空间复杂度0(1)

0 赞同 0 条回复

浅伤永久会员 2023年6月28日下午4:34

时间复杂度O(n)
空间复杂度O(n)
遍历链表得到长度，创建等长数组
再次遍历倒序输入数组

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode temp = head;
        int len = 0;
        while(temp!=null && len++>=0) temp = temp.next;

        int[] result = new int[len];

        temp = head;
        while(temp!=null){
            result[len - 1] = temp.val;
            len--;
            temp = temp.next;
        }
        return result;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月28日下午1:51

java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        /*
        采用数组从后往前放的方式，还可以采用递归和栈等形式
        时间复杂度是O(n), 空间复杂度是O(n)
        */
        if(head == null) {
            return new int[0];
        }
        int cnt = 0;
        ListNode temp = head;
        while(temp != null) {
            cnt ++;
            temp = temp.next;
        }
        int arr[] = new int[cnt];
        temp = head;
        while(cnt > 0) {
            arr[--cnt] = temp.val;
            temp = temp.next;
        }
        return arr;
    }
}

0 赞同 0 条回复

大大普通 2023年6月28日上午11:01

java:
//递归
 class Solution {

    int i=0;//用来表示数组大小，从而开辟数组
    int j=0;//用来标记下标位置
    int[] res;
    public int[] reversePrint(ListNode head) {
        solve(head);
        return res;           
    }
    void solve(ListNode head){
      if(head==null){//尾节点
           res=new int[i];
           return ;
       }
       i++;//节点个数
       solve(head.next);
       res[j++]=head.val;
    }
 }



//C++
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
     //栈
      stack <int> p;
        vector<int>a;
        while(head){
            p.push(head->val);
            head=head->next;
        }
        while(!p.empty()){
            a.push_back(p.top());
            p.pop();
        }
        return a;    
    }
};

0 赞同 0 条回复

泡芙永久会员 2023年6月27日下午8:02

方法一：递归

Time：O(n)

Space：O(n)

class Solution {
    public int[] reversePrint(ListNode head) {
        traverse(head);
        return res;
    }

    // 记录链表长度
    int len = 0;
    // 初始化数组
    int[] res;
    // 数组中的指针
    int p = 0;

    // 递归遍历单链表
    void traverse(ListNode head) {
        if (head == null) {
            // 到达链表尾部，此时知道了链表的总长度
            // 创建数组
            res = new int[len];
            return;
        }
        len++;
        traverse(head.next);
        // 后序位置，可以倒序操作链表
        res[p] = head.val;
        p++;
    }
}

方法二：从右到左进行遍历

Time：O(n)

Space：O(1)

class Solution {
    public int[] reversePrint(ListNode head) {
        // 如果 head 为null 返回空数组
        if (head == null) {
            return new int[0];
        }
        // 统计节点个数
        int len = 0;
        // 暂存头节点
        ListNode tmp = head;
        while (tmp != null) {
            count ++;
            tmp = tmp.next;
        }
        // 创建数组
        int[] res = new int[len];
        int k = len - 1;
        // 从右往左遍历进入数组
        while (head != null) {
            res[k--] = head.val;
            head = head.next;
        }
        return res;
    }
}

0 赞同 0 条回复

Yangon 普通 2023年6月27日下午5:48

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {

        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode temp = head;
        while(temp != null){
            stack.push(temp);
            temp = temp.next;

        }

        int size = stack.size();
        int[] print = new int[size];
        for(int i = 0; i < size; i++){
            print[i] = stack.pop().val;
        }

        return print;


    }
}

堆栈

0 赞同 0 条回复

mpweixin用户普通 2023年6月26日下午10:09

class Solution:
    def reversePrint(self, head: 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

创建一个新数组res，倒着向数组中填入链表元素值

0 赞同 0 条回复

baoyou 普通 2023年6月26日上午12:46

/**
 * 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];
        }
        ListNode temp = head;
        int count = 0;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        int[] result = new int[count];
        int idx = count - 1;
        while (head != null) {
            result[idx--] = head.val;
            head = head.next;
        }
        return result;
    }
}

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

0 赞同 0 条回复

HU 普通 2023年6月25日上午11:39

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function(head) {
    // 如果为空链表，则返回空数组
    if(head === null) {
        return [];
    }
    // 统计链表节点个数，方便创建数组
    let count = 0;
    let temp = head;
    while(temp) {
        count++;
        temp = temp.next;
    }
    let res = new Array(count);
    let k = count - 1;
    // 从数组末尾开始填充数字
    while(k >= 0) {
        res[k--] = head.val;
        head = head.next;
    }
    return res;
};

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

0 赞同 0 条回复

往远处看普通 2023年6月25日上午8:55

解题思路

将链表压入容器当中，可以实现快速的反转。
V.push_back(A->val);
reverse(V.begin(),V.end());

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        ListNode *A = head;
        vector<int> V;
        while(A)
        {
            V.push_back(A->val);
            A = A->next;
        }
        reverse(V.begin(),V.end());
        return V;



    }
};

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

0 赞同 0 条回复

未来已来~ 普通 2023年6月24日下午12:12

/** 
 * Java 代码
 * 思路: 从左往右反向填充数组
 * 复杂度分析:
 *      时间复杂度: O(n)
 *      空间复杂度: O(1)
 * 
 * 待补充:
 *      递归法
 *      辅助栈
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null) {
            return new int[0]; // 链表为空时返回一个空数组
        }
        // 统计链表节点个数,便于创建合理长度数组
        int length = 0;
        ListNode temp = head;
        while (temp != null) {
            temp = temp.next;
            length++;
        }
        int[] result = new int[length]; // 避免数组长度不够或长度过长
        // 从左往右反向填充数组
        for (int resSize = length - 1; resSize >= 0; resSize--) {
            result[resSize] = head.val;
            head = head.next;
        }
        return result;
    }
}

0 赞同 0 条回复

BOZ 普通 2023年6月24日上午11:11

【思路】递归法，内存消耗偏高
【复杂度】时间O(n)，空间复杂度O(n)

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if (head == NULL) return vector<int>();
        auto reverseVal = reversePrint(head->next);
        reverseVal.push_back(head->val);
        return reverseVal;
    }
};

0 赞同 0 条回复

GGBond 普通 2023年6月23日下午9:09

class Solution {
    public int[] reversePrint(ListNode head) {
        Deque<Integer> stack = new LinkedList<>();
        ListNode p = head;
        while(p != null){
            //头插法
            stack.addFirst(p.val);
            p = p.next;
        }
        return stack.stream().mapToInt(e->e).toArray();
    }

}

//递归
class Solution {
    public int[] reversePrint(ListNode head) {
        print(head);
        return res.stream().mapToInt(e->e).toArray();
    }
    List<Integer> res = new ArrayList<>();
    public void print(ListNode node){
        if(node == null){
            return;
        }
        print(node.next);
        res.add(node.val);
    }
}

0 赞同 0 条回复

Tang 普通 2023年6月23日下午6:46

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> tmp = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        if (head == null) {
            return new int[0];
        }
        reverse(head);
        int[] res = new int[tmp.size()];
        for (int i = 0; i < tmp.size(); i++) {
        res[i] = tmp.get(i);
        }
        return res;
    }

    public void reverse(ListNode head) {
        if (head.next != null) {
            reverse(head.next);
        }
        tmp.add(head.val);
    }
}

利用递归实现。时间复杂度：O(n) 空间复杂度：O(n)

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月23日下午4:33

打卡

var reversePrint = function(head) {
    let arr = [];
    if(head == null){
        return arr;
    }
    let cur = head;
    while( cur != null){
        arr.push(cur.val);
        cur = cur.next;
    }
    arr.reverse()
    return arr;
};

0 赞同 0 条回复

WhyBeBubble 普通 2023年6月22日下午11:10

class Solution { // cpp实现
private:
    vector<int> res;
public:
    void helper(ListNode* head) {
        if(!head) return;
        helper(head->next);
        res.push_back(head->val);
    }

    vector<int> reversePrint(ListNode* head) {
       helper(head);
       return res;
    }
};

0 赞同 0 条回复

Yodl. 普通 2023年6月22日下午9:25

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> ans;
    void fun(ListNode* p)
    {
        if(p->next!=NULL)
        {
            fun(p->next);
        }
        ans.push_back(p->val);
    }
    vector<int> reversePrint(ListNode* head) {
        ListNode *p=head;
        if(p==NULL)
        {
            return ans;
        }
        fun(p);
        return ans;
    }
};

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

0 赞同 0 条回复

Tlhey 普通 2023年6月22日下午8:56

“` C++
注意可能给一个元素的列表，所以一开始定义head->next的时候要特判是不是nullptr
class Solution {
public:
vector reversePrint(ListNode* head) {
ListNode* cur = head;
vector ans;
if(head == nullptr) return ans;
ListNode *pre1 = head -> next;
while(pre1 != nullptr){
ListNode* pre2 = nullptr;
if(pre1 -> next !=nullptr) pre2 = pre1->next;
pre1->next = cur;
cur = pre1;
pre1 = pre2;
}
head->next = nullptr;
while(cur != nullptr){
ans.push_back(cur->val);
cur = cur ->next;
}
return ans;
}
};
“`

0 赞同 0 条回复

mpweixin用户普通 2023年6月22日下午8:52

数组反向填充

“`C#
public class Solution {
public int[] ReversePrint(ListNode head) {

    if(head == null){
        return new int[0];
    }
    ListNode temp = head;
    int count = 0;
    while(temp != null){
        count++;
        temp = temp.next;
    }

    int[] array = new int[count];
    int k = count -1;
    temp = head;

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

    return array;
}

}

“`

0 赞同 0 条回复

mpweixin用户普通 2023年6月22日下午4:17

递归 时间复杂度O(n) 空间复杂度O(n)
# 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]:
        if not head:
            return []
        return self.reversePrint(head.next) + [head.val]

0 赞同 0 条回复

3_🔥 永久会员 2023年6月22日下午3:34

class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null) return new int[0];
        ListNode temp = head;
        int count = 0;
        while(temp!=null){
            count++;
            temp = temp.next;
        }
        int k = count -1;
        int rev[] = new int[count];
        while(head!=null){
            rev[k--] = head.val;
            head = head.next;
        }
        return rev;
    }
}

翻转数组实现
时间复杂度O（n）空间O（1）

0 赞同 0 条回复

&Camille 普通 2023年6月22日下午3:32

class Solution {
public int[] reversePrint(ListNode head) {
Stack stack = new Stack();
ListNode temp = head;

    //入栈
    while (temp != null) {
        stack.push(temp);
        temp = temp.next;
    }

    //根据栈的长度创建数组
    int size = stack.size();
    int[] print = new int[size];

    //出栈
    for (int i = 0; i < size; i++) {
        print[i] = stack.pop().val;
    }
    return print;
}

}

0 赞同 0 条回复

CV大神普通 2023年6月22日上午12:45

public int[] reversePrint(ListNode head) {
        LinkedList<ListNode> stack = new LinkedList<ListNode>();
        ListNode current = head;
        //遍历，全部塞到栈里
        while (current != null) {
            stack.addLast(current);
            current = current.next;
        }
        int[] reverseResult = new int[stack.size()];
        //再次遍历栈，放到数组
        for (int i = 0; i < reverseResult.length; i++) {
            reverseResult[i] = stack.pollLast().val;
        }
        return reverseResult;
    }

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

0 赞同 0 条回复

别恰冰水🧊 永久会员 2023年6月21日下午11:01

“`C
int* reversePrint(struct ListNode* head, int* returnSize){
if(head == NULL){
*returnSize=0;
return NULL;
}

    // 统计链表节点个数，方便创建数组
    int count = 0;
    struct ListNode* temp = head;
    while(temp != NULL){
        count++;
        temp = temp->next;
    }

    int *res=(int *)malloc(sizeof(int)*count);
    int k = count - 1;
    // 从右往左填充数组
    while(head != NULL){
        res[k--] = head->val;
        head = head->next;
    }
    return res;

}

0 赞同 0 条回复

mpweixin用户普通 2023年6月21日下午6:33

int* reversePrint(struct ListNode* head, int* returnSize){
    int stack[100000];                                       //辅助栈
    int top = 0;                                            //栈顶指针
    struct ListNode *q = head;
    while(q != NULL){                                       //遍历链表并将每个结点值压入栈
        stack[top++] = q->val;
        q = q->next;
    }
    *returnSize = top;
    int* res = (int*)malloc(sizeof(int) * (*returnSize));
    for(int i=top-1, j=0; i >= 0; --i, ++j)                 //将栈中的元素从栈顶开始取出依次存入数组
        res[j] = stack[i];
    return res;
}

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

0 赞同 0 条回复

mpweixin用户普通 2023年6月21日下午4:02

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]:
        # res = []
        # while head:
        #     res.insert(0, head.val)
        #     head = head.next
        # return res
        res = []
        while head:
            res += [head.val]
            head = head.next
        return res[::-1]

0 赞同 0 条回复

Dsjh 普通 2023年6月21日下午3:42

“`c++
// c++实现
class Solution {
public:
vector reversePrint(ListNode* head) {
vector ans;
while(head){
ans.insert(ans.begin(),head->val);
head = head->next;
}
return ans;
}
};

0 赞同 0 条回复

断舍离永久会员 2023年6月21日下午2:51

class Solution {
    public int[] reversePrint(ListNode head) {
            //用于存放链表值的集合
        ArrayList list = new ArrayList();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        Collections.reverse(list);
        int arr[] = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            arr[i] = list.get(i);
        }
        return arr;
    }
}

0 赞同 0 条回复

普通 2023年6月21日下午2:24

class Solution {
    public int[] reversePrint(ListNode head) {
        List<Integer> nodeValList = new ArrayList<>();
        while(head != null){
            nodeValList.add(head.val);
            head = head.next;
        }
        int[] result = new int[nodeValList.size()];
        int index = 0;
        for(int i=nodeValList.size()-1;i>=0;i--){
            result[index] = nodeValList.get(i);
            index++;
        }
        return result;
    }
}

时间复杂度O(n)

0 赞同 0 条回复

小吕普通 2023年6月21日下午1:57

cpp实现
void returnresult(ListNode* cur,vector& result)
{
if(cur->next!=NULL)
{
returnresult(cur->next,result);
}
result.push_back(cur->val);
}
vector reversePrint(ListNode* head) {
vector result;
ListNode* cur = head;
if(curNULL)return result;
returnresult(cur,result);
return result;
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月21日下午12:13

利用栈

class Solution {
public:

    vector<int> reversePrint(ListNode* head) {
        ListNode *cur = head;
        vector<int> temp;
        vector<int> result;

        if(head == NULL) return result; 

        while(cur != NULL){
            temp.push_back(cur -> val);
            cur = cur -> next;
        }

        while(!temp.empty()){
            result.push_back(temp.back());
            temp.pop_back();
        }
        return result;
    }
};

利用逆向填充数组

class Solution {
public:

    vector<int> reversePrint(ListNode* head) {
        if(head == NULL) return {}; 
        int count = 0;

        ListNode *cur = head;
        while(cur != NULL){
            count++;
            cur = cur -> next;
        }

        //定义一个数组
        vector<int> result(count);

        while(head){
            result[count - 1] = head -> val;
            head = head -> next;
            count--;
        }
        return result;

    }
};

0 赞同 0 条回复

悠若普通 2023年6月21日上午10:59

利用栈的先入后出特性，将链表节点值依次放入栈中，再依次出栈存入数组

class Solution {
    public int[] reversePrint(ListNode head) {  
        if(head == null){
            return null;
        }
        Stack<Integer> stack = new Stack<>(); 
        while(head != null){
            stack.push(head.val);
            head = head.next;
        }
        int[] arr = new int[stack.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = stack.pop();
        }
        return arr;
    }
}

0 赞同 0 条回复

Bello~ 普通 2023年6月21日上午10:35

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

class Solution {
    public int[] reversePrint(ListNode head) {
        if (head == null) {
            return new int[0];
        }
        Stack stack = new Stack<>();
        ListNode cur = head;
        int n = 0;
        while(cur != null) {
            stack.push(cur.val);
            cur = cur.next;
            n++;
        }
        int[] result = new int[n];
        for(int i = 0; i < n; i++) {
            result[i] = stack.pop();
        }
        return result;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月21日上午10:24

class Solution {
    public int[] reversePrint(ListNode head) {
        LinkedList<Integer> stack = new LinkedList<>();
        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 ;
    }
}

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

0 赞同 0 条回复

名字什么的好麻烦普通 2023年6月21日上午10:18

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

class Solution {
    public int[] reversePrint(ListNode head) {
        int count=0;
        ListNode temp=head;
        while(temp!=null){
            count++;
            temp=temp.next;
        }
        int[] ans = new int[count];
        count--;
        while(head!=null){
            ans[count--]=head.val;
            head=head.next;
        }
        return ans;
    }
}

0 赞同 0 条回复

花老爷普通 2023年6月21日上午7:50

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

class Solution {
    public int[] reversePrint(ListNode head) {
        List<Integer> resList = new ArrayList<>();
        reverse(resList, head);
        int[] res = new int[resList.size()];
        int count = 0;
        for (int val: resList) {
            res[count++] = val;
        }
        return res;
    }

    private void reverse(List<Integer> resList, ListNode cur) {
        if (cur == null) {
            return;
        }
        reverse(resList, cur.next);
        resList.add(cur.val);
    }
}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月21日上午7:28

# 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]:
        if not head:
            return []

        res = self.reversePrint(head.next)
        res.append(head.val)

        return res

时间复杂度O(n)

0 赞同 0 条回复

mpweixin用户普通 2023年6月21日上午6:34

C++ 两种方法:
1. 递归
TC: O(n)
SC: O(n)

“`c++
class Solution {
vectorres;
public:
vector reversePrint(ListNode* head) {
printReverse(head);
return res;
}
void printReverse(ListNode* curr) {
if (!curr) {
return;
}
printReverse(curr->next);
res.push_back(curr->val);
}
};

方法二: 反转链表之后再遍历放入数组
TC: O(n)
SC: O(1)
```c++
class Solution {
public:
    vector reversePrint(ListNode* head) {
        vectorres;
        ListNode* prev = NULL;
        ListNode* curr = head;
        while (curr) {
            ListNode *temp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = temp;
        }
        while (prev) {
            res.push_back(prev->val);
            prev = prev->next;
        }
        return res;
    }
};

0 赞同 0 条回复

　　　　　　　　普通 2023年6月21日上午3:02

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

【时间O(n),空间O(n)】
依次访问并插入vector中
翻转vector

0 赞同 0 条回复

残月冷骄阳普通 2023年6月21日上午12:44

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    ArrayList<Integer> tempList = new ArrayList<>();
//递归调用法
    public int[] reversePrint(ListNode head) {
        recur(head);
         int[] res =   new int[tempList.size()];
         for (int i=0;i< tempList.size() ; i++){
             res[i] = tempList.get(i);
         }
         return res;

    }

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

0 赞同 0 条回复

Jerry 普通 2023年6月20日下午11:36

public class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
    ArrayList<Integer> res = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    void recur(ListNode head) {
        if (head == null) return; //到达尾部，终止递归
        recur(head.next);
        res.add(head.val);
    }
}

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

0 赞同 0 条回复

大鑫啊普通 2023年6月20日下午11:25

时间复杂度：O(n)
空间复杂度：O(1)
1、先判空
2、计算待反转链表的长度
3、new一个等长的数组，将链表从头开始放在数组的尾部，往前填充

class Solution {
    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[] rearr =new int[count];
        int k = count-1;
        while(head != null){
            rearr[k--] = head.val;
            head = head.next;
        }
        return rearr;
    }
}

0 赞同 0 条回复

zll 普通 2023年6月20日下午11:12

时间复杂度O（n）；
空间复杂度O（n）；

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* reversePrint(struct ListNode* head, int* returnSize){
    struct ListNode *p;
    p=head;
    int count=0;
    while(p){
        count++;
        p=p->next;
    }
    *returnSize=count;
    int *q=(int*)malloc(sizeof(int)*count);
    reverse(head,count-1,q);
    return q;
}


void reverse(struct ListNode *head,int t,int* returnSize){
    if(!head){
        return ;
    }
    reverse(head->next,t-1,returnSize);
    returnSize[t]=head->val;
}

0 赞同 0 条回复

局外人普通 2023年6月20日下午11:10

思路：递归——借鉴树的后序遍历，先不断递归到下一个节点，当遇到空指针才会结束递归，依次弹出之前递归栈中的东西，以此作为翻转的结果
时间复杂度：O(n)，空间复杂度：O(n)

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> res={};
        recurse(head, res);
        return res;
    }

    void recurse(ListNode* head, vector<int>& res){
        if(head==NULL) return;
        recurse(head->next, res);
        res.push_back(head->val);
    }
};

0 赞同 0 条回复

阿白普通 2023年6月20日下午10:24

思路：先遍历一遍链表计算长度，再遍历一遍链表反向填入数组中
时间复杂度O(n),空间复杂度O(1)

class Solution {
    public int[] reversePrint(ListNode head) {
        int size = 0;
        ListNode tmp = head;
        while(tmp != null){
            size++;
            tmp = tmp.next;
        }
        int[] print = new int[size];
        tmp = head;
        while(tmp != null) {
            print[--size] = tmp.val;
            tmp = tmp.next; 
        }
        return print;

    }
}

0 赞同 0 条回复

江畅普通 2023年6月20日下午10:21

class Solution {
public:
    // 方法一：栈
    // 时间复杂度 O(N)
    // 空间复杂度 O(N)
    vector<int> reversePrint(ListNode* head) {
        vector<int> res;
        stack<int> nodes;

        ListNode* tmp = head;
        while (tmp != nullptr) {
            nodes.push(tmp->val);
            tmp = tmp->next;
        }

        while (!nodes.empty()) {
            res.push_back(nodes.top());
            nodes.pop();
        }

        return res;
    }
};   

class Solution { 
private:
    vector<int> res;
public:
    // 方法二：递归
    // 时间复杂度 O(N)
    // 空间复杂度 O(N)
    vector<int> reversePrint(ListNode* head) {
        if (head != nullptr) {
            reversePrint(head->next);
            res.push_back(head->val);
        }
        return res;
    }
};

class Solution {
public:    
    // 方法三：原地
    // 时间复杂度 O(N)
    // 空间复杂度 O(1) 
    vector<int> reversePrint(ListNode* head) {
        if (head == nullptr) return {};

        int cnt = 0;
        ListNode* tmp = head;
        while (tmp != nullptr) {
            ++cnt;
            tmp = tmp->next;
        }

        vector<int> res(cnt);

        // while (cnt > 0) {
        while (head != nullptr) {
            res[cnt - 1] = head->val;
            --cnt;
            head = head->next;
        }
        return res;
    }
};

0 赞同 0 条回复

拾陆. 普通 2023年6月20日下午10:00

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector reversePrint(ListNode head) {
vector result;
if(!head) return result;
ListNode* cur = head;
ListNode* pre = nullptr;
while(cur){
ListNode *node = cur->next;
cur->next = pre;
pre = cur;
cur = node;
}
while(pre){
result.push_back(pre->val);
pre = pre->next;
}
return result;
}
};
可以

0 赞同 0 条回复

yxy 普通 2023年6月20日下午9:43

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> res;
    void foo(ListNode* cur)
    {
        if(!cur) return;
        foo(cur->next);
        res.push_back(cur->val);
    }
    vector<int> reversePrint(ListNode* head) {
        foo(head);
        return res;
    }
};

简单

0 赞同 0 条回复

désire. 普通 2023年6月20日下午9:40

C++：原地反转链表+顺序遍历
class Solution {
public:
vector reversePrint(ListNode* head) {
vector vec(0);
if(head NULL) return vec;
ListNode* cur = head;
ListNode* tmp;
ListNode* pre = NULL;
while(cur){
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
while(pre){
vec.push_back(pre->val);
pre = pre->next;
}
return vec;
}
};

0 赞同 0 条回复

跋扈疙瘩汤普通 2023年6月20日下午9:36

反转链表多加了一项将节点内存储的数据插入数组中

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        ListNode* temp;
        ListNode* cur = head;
        ListNode* pre = nullptr;
        vector<int> nums;
        while (cur) {
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        while (pre) {
            nums.push_back(pre->val);
            pre = pre->next;
        }
        return nums;
    }
};

0 赞同 0 条回复

怀瑾永久会员 2023年6月20日下午9:31

C++
执行用时：4 ms
内存消耗：11.3 MB
从尾到头打印链表：
使用递归完成，由于需要使用数组返回，所以新建一个vector数组，如果该节点的下一个节点没有指向NULL的话，继续调用该函数，当条件不符时，就将该节点的值放入数组中，最后返回该数组即可。

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> n;
        if(head == NULL) return n;
        if(head->next !=NULL){
            n = reversePrint(head->next);   
        }
        n.push_back(head->val);
        return n;
    }
};

0 赞同 0 条回复

硬核洋葱普通 2023年6月20日下午9:26

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> ans;
        if(!head)   return ans;
        recur_rPrint(head, ans);
        return ans;
    }

    void recur_rPrint(ListNode* p, vector<int>& ans){
        if(p->next)
            recur_rPrint(p->next, ans);
        ans.push_back(p->val);
    }
};

时间复杂度O(n)，空间复杂度O(n)
单链表只能从前往后遍历，不支持从后往前遍历，这时候选择栈来辅助，也可以选择用递归。这里用递归

0 赞同 0 条回复

～普通 2023年6月20日下午9:19

方法一：
递归
class Solution {
public:
vector reversePrint(ListNode* head) {
//base case
if(head nullptr){
return {};
}
//把子链表翻转结果算出来
vector subprint = reversePrint(head->next);
//加上头部指针指向的值
subprint.push_back(head->val);
return subprint;
}
}；
class Solution {
vector res;
int len = 0;
int p = 0;
public:
vector reversePrint(ListNode* head) {
traverse(head);
return res;
}
void traverse(ListNode* head){
if(head nullptr){
// 到达链表尾部，此时知道了链表的总长度
// 创建结果数组
res.resize(len);
return;
}
len++;
traverse(head->next);
//后序位置，可以倒序操作链表
res[p] = head->val;
p++;
}
};
栈方法
class Solution {
vector res;
int len = 0;
int p = 0;
public:
vector reversePrint(ListNode* head) {
stack<ListNode> stack;
vector res;
while(head){
stack.push(head);
head = head->next;
}
while(!stack.empty()){
ListNode cur = stack.top();
stack.pop();
res.push_back(cur->val);
}
return res;
}
};

0 赞同 0 条回复

* 普通 2023年6月20日下午9:11

c实现
int* reversePrint(struct ListNode* head, int* returnSize){ if(!head){ returnSize=0; return malloc(sizeof(int)10000); } int * ans=reversePrint(head->next,returnSize); ans[(*returnSize)++]=head->val; return ans;}

0 赞同 0 条回复

张君雅小妹妹普通 2023年6月20日下午8:49

思路：
s1. 通过递归将Node值存到List里；
s2. 将list转化为数组。
时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    public int[] reversePrint(ListNode head) {
        List<Integer> nodes = new ArrayList<>();
        printNode(head, nodes);
        int[] nodeArr = new int[nodes.size()];
        for(int i = 0; i < nodes.size(); i++){
            nodeArr[i] = nodes.get(i);
        }
        return nodeArr;
    }

    public void printNode(ListNode head, List<Integer> nodes){
        if(head == null) return;
        printNode(head.next, nodes);
        nodes.add(head.val);
    }
}

0 赞同 0 条回复

哈哈哈普通 2023年6月20日下午8:40

思路：首先计算出链表的长度，然后创建数组，反向向数组添加链表的val值（也可以利用stack进行实现，但是代码太复杂）
时间复杂度为O（n）,空间复杂度为O（n）

class Solution {
    public int[] reversePrint(ListNode head) {
      //利用递归得到
      //1. 首先进行遍历得到长度
      //2. 然后再进行遍历，反向输出。时间复杂度为O（n），空间复杂度为O（n）
      int count=0;
      ListNode head1=head;
      while(head1!=null){
          count++;
          head1=head1.next;
      }
      int[] a=new int[count];
      while(head!=null){
          a[count-1]=head.val;
          head=head.next;
          count--;
      }
      return a;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月20日下午8:37

C++实现

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int>v;
        stack<int> s;
        while (head){
            s.push(head->val);
            head=head->next;
        }
        while(!s.empty()){
            v.push_back(s.top());
            s.pop();
        }
        return v;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年6月20日下午8:35

思路：
采用递归的方法，递归的终止条件是只要递归不为空，递归的顺序就是和采用入栈的顺序是一样的。

“`c++
class Solution {
public:
vector reversePrint(ListNode* head) {
if(!head){
return {};
}
vector NewStack = reversePrint(head->next);
NewStack.push_back(head->val);
return NewStack;
}
};

0 赞同 0 条回复

伏月三十普通 2023年6月20日下午8:26

1.用栈来实现
class Solution {
public int[] reversePrint(ListNode head) {
if(headnull){
return new int[0];
}
Deque stack=new ArrayDeque<>();
int size=0;
while(head!=null){
stack.push(head);
head=head.next;
size++;
}

    int[] array=new int[size];
    for(int i=0;i<array.length;i++){
        ListNode temp =stack.pop();
        array[i]=temp.val;
    }
    return array;

}

}

2.递归实现
class Solution {
public int[] reversePrint(ListNode head) {
if(headnull){
return new int[0];
}

    ListNode h1=head;
    //注意求链表长度的要放在反转前面，不然head就只指向一个节点了  算下来的size就是1  要不然就放后面用反转后的算
    int size=0;
    while(h1!=null){
        size++;
        h1=h1.next;
    }

    ListNode last=reverse(head);
    //定义两个头节点  防止把head和last改了
    ListNode l1=last;
    int[] array=new int[size];
    for(int i=0;i<array.length;i++){
        array[i]=l1.val;
        l1=l1.next;
    }
    return array;  
}

private ListNode reverse(ListNode head){
    if(head==null || head.next==null){
        return head;
    }
    ListNode last=reverse(head.next);
    head.next.next=head;
    head.next=null;
    return last;
}

}
真的会谢，忘得一干二净

0 赞同 0 条回复

张开怀普通 2023年6月20日下午8:21

class Solution{
public:
     vector<int> reversePrint(ListNode* head){
           if(!head)
               return { };
           // 统计结点个数，用于创建数组
           int count=0;
           ListNode* temp = head;
           while(temp){
                count++;
                temp = temp->next;
            }
            vector<int> res(count);
            int k = count-1;
            // 从右往左填充数组
            while(head){
                 res[k--] = head->val;
                 head = head->next;
            }
            return res;
     }
}

从左向右遍历原数组，在新数组中从右向左进行存储
时间复杂度：O(n)，空间复杂度：O(1)

0 赞同 0 条回复

jhfuture 普通 2023年6月20日下午8:11

java实现

 //1.逆向思维，从右到左进行。
    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[] array=new int[count];
        // int k=count-1;
        // while(head!=null){
        //     array[k--]=head.val;
        //     head=head.next;
        // }
        // return array;

        // 2.递归的方法解决
        //2.1使用list，反向加入计科。
        List<Integer> l1=new ArrayList<Integer>();
        reserver(head,l1);
        int []array= new int[l1.size()];
        for(int i=0;i<l1.size();i++){
            array[i]=l1.get(i);
        }
        return array;
    }
    public void reserver(ListNode node,List l){
        if(node==null){
            return;
        }
        reserver(node.next,l);
        l.add(node.val);
    }

时间复杂度：n，空间复杂度为n。
思路：第一种解法是帅地的逆序，第二种是使用递归的方法，并结合list。

0 赞同 0 条回复

Vow the vow。普通 2023年6月20日下午8:00

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

// 法一：栈
    // public int[] reversePrint(ListNode head) {
    //     Stack<Integer> stack = new Stack<>();
    //     while(head != null){
    //         stack.push(head.val);
    //         head = head.next;
    //     }
    //     int[] res = new int[stack.size()];
    //     int index = 0;
    //     while(!stack.isEmpty()){
    //         res[index++] = stack.pop();
    //     }
    //     return res;
    // }

    // 法二：
    List<Integer> list = new ArrayList<>();
    public int[] reversePrint(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;
        reversePrint(head.next);
        list.add(head.val);
    }

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月20日下午7:52

//时间复杂度O(n)，空间O(1)
public int[] reversePrint(ListNode head) {
    if(head == null){
        return new int[]{};
    }

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

    int[] result = new int[count];
    cur = head;
    while(cur != null){
        result[--count] = cur.val;
        cur = cur.next;
    }

    return result;
}

0 赞同 0 条回复

彦，，# 普通 2023年6月20日下午7:48

递归算法

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> result;
        if (head) {
            result = reversePrint(head->next);
            result.push_back(head->val);
        }
        return result;
    }
};

0 赞同 0 条回复

peach 普通 2023年6月20日下午6:52

思路

考虑三种方法，直接计算长度，给出数组，倒序遍历即可
或者使用辅助栈、递归逻辑

代码

 //思路一。先拿到链表长度，然后建立数组，遍历链表，倒序把val放入数组中
 //时间复杂度O(2n), 空间复杂度O(1)(数组是O(n)，没有额外空间)
class Solution {
    public int[] reversePrint(ListNode head) {
        int[] res = new int[getLen(head)];
        for(int i = res.length - 1;i >= 0; i--){
            res[i] = head.val;
            head = head.next;
        }
        return res;
    }
    private int getLen(ListNode head){
        int res = 0;
        while(head != null){
            head = head.next;
            res++;
        }
        return res;
    }
}
 //使用辅助栈，遍历链表，元素入栈，然后size就是数组长度，再遍历栈即可
 //时间复杂度O(2n), 空间复杂度O(2n)(使用额外栈，空间O(n))
class Solution {
    public int[] reversePrint(ListNode head) {
        Deque<Integer> stack = new ArrayDeque();
        while(head != null){
            stack.addFirst(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for(int i = 0; i < res.length; i++){
            res[i] = stack.removeFirst();
        }
        return res;
    }
}
 //使用递归处理
 //和栈的时间复杂度空间复杂度相同
class Solution {
    List<Integer> list = new ArrayList();
    public int[] reversePrint(ListNode head) {
        recur(head);
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
    private void recur(ListNode head){ //递归，回溯逻辑
        if(head == null) return; //终止条件，如果head为空，结束递归
        recur(head.next); //先递归
        list.add(head.val); //最后再把这个val加入集合，保证倒序
    }
}

1 赞同 0 条回复

行动派小彩笔普通 2023年6月20日下午6:38

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

 /*
 // 递归解法 时间O(n)-访问所有节点， 空间O(n)-递归深度就是链表长度
 // 递归到最底层节点，从后向前把元素放入vector容器中
class Solution {
public:
    void dfs(vector& num,ListNode* node)
    {
        if(node==NULL) return;
        dfs(num,node->next);
        num.push_back(node->val);
    }
    vector reversePrint(ListNode* head) {
        vector vec;
        dfs(vec,head);
        return vec;
    }
};
*/

 //计算链表节点数，从右向左遍历的存放节点值
 // 时间复杂度两次遍历循环O(n),空间复杂度O(1),没有额外空间
class Solution {
public: 
    vector reversePrint(ListNode* head) {
        if(head==NULL) return {};

        ListNode* cur = head;
        int count = 0;
        while(cur!=NULL)
        {
            ++count;
            cur = cur->next;

        }
        vector vec(count,0);
        cur = head;
        for(int i=count-1;i>=0;--i)
        {
            vec[i] = cur->val;
            cur = cur->next;
        }
        return vec;
    }
};

0 赞同 0 条回复

钱杰普通 2023年6月20日下午5:42

class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
if not head:
return []
temp=head
count=0
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
”’
1判断这个链表是否为空，也就是头结点head是否为空，如果为空，直接返回[]
2添加一个指针temp，指向head,另外设置一个计数count,初始化为0
3判断指针是否为空，也就是指针有没有对象，用while表循环，在这个范围内，如果指针不为空，也就是指着对象，用count+1表示增加一个数，然后指针往后面走一步，直到指针为空，用count统计对象数
4接下来创建一个新的列表，用[0]count表示一个列表中有count个0元素
5建立一个索引k,也就是等于count-1
6然后索引不断往前走，head往后走，这样就把内容倒着输入进去了
7返回res列表
时间复杂度：O(n) 额外空间复杂度：O(1)

'''

0 赞同 0 条回复

Ming 普通 2023年6月20日下午5:01

这里是Ming的打卡：
思路1：遍历链表将值存入集合，再将集合反转，把值存入数组

/**
 * 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[]{};
       ListNode temp = head;
       //由于不知道链表长度，使用集合存储数据
       List<Integer> list = new ArrayList<>();
       while(temp != null) {
           list.add(temp.val);
           temp = temp.next;
       }
       //利用API反转集合
       Collections.reverse(list);
       //数组接收数据返回
       int[] arr = new int[list.size()];
       for(int i = 0; i < list.size(); i++) {
           arr[i] = list.get(i);
       }
       return arr;
    }
}

思路2：反正会将链表遍历一遍，得到他的长度再建数组，从后往前给数组赋值

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode temp = head;
        int count = 0;
        while(temp != null) {
            count++;
            temp = temp.next;
        }
        int[] arr = new int[count];
        //使temp重新指向头结点
        temp = head;
        for(int i = count - 1; i >= 0; i--) {
            arr[i] = temp.val;
            temp = temp.next;
        }
        return arr;
    }
}

0 赞同 0 条回复

雨落圆荷普通 2023年6月20日下午4:37

public int[] reversePrint(ListNode head){
if(headnull){
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)

0 赞同 0 条回复

mpweixin用户普通 2023年6月20日下午4:34

class Solution {
public:
    void func(ListNode *node,vector<int> &v)
    {
        if(node==nullptr)
        {
            return;
        }
        else
        {
            func(node->next,v);
            v.push_back(node->val);
        }
    }
    vector<int> reversePrint(ListNode* head) {
        vector<int> v;
        func(head,v);
        return v;
    }
};

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

0 赞同 0 条回复

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

共以下 82 个回答

方法一：递归

方法二：从右到左进行遍历

解题思路

代码

思路

代码

# 回答此问题取消回复

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

共以下 82 个回答

方法一：递归

方法二：从右到左进行遍历

解题思路

代码

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复