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

CrazyJavaBoy 永久会员 2023年3月24日上午9:44

打破惯性思维数组从尾到头存放

class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null) {
            return new int[0];
        }
        ListNode cur = head;
        int length = 0;
        //统计链表长度
        while(cur != null) {
            length++;
            cur = cur.next;
        }
        cur = head;
        int[] res = new int[length];
        //从头到尾遍历链表  数组从尾到头存放
        for(int i = length-1; i >= 0; i--) {
            res[i] = cur.val;
            cur = cur.next;
        }
        return res;
    }
}

0 赞同 0 条回复

lucca 普通 2022年12月30日上午1: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) {
        List<Integer> tmp = new ArrayList<>(10010);
        rev(head, tmp);
        int[] ans = new int[tmp.size()];
        for (int i = 0; i < tmp.size(); i++) {
            ans[i] = tmp.get(i);
        }
        return ans;
    }

    private void rev(ListNode p, List<Integer> list) {
        if (p == null) return;

        rev(p.next, list);
        list.add(p.val);
    }
}

栈

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        int[] s = new int[10010];
        int top = -1;
        while (head != null) {
            s[++top] = head.val;
            head = head.next;
        }
        int[] ans = new int[top+1];
        int idx = 0;
        while (top != -1) ans[idx++] = s[top--];
        return ans;
    }
}

0 赞同 0 条回复

糖鑫普通 2022年12月2日下午11:13

/**
 * 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 cur=head;
        ListNode prev=null;
        ListNode tmp;
        int n=0;
        while(cur!=null){
            tmp=cur.next;
            cur.next=prev;
            prev=cur;
            cur=tmp;
            n++;
        }
        int reverse[]=new int[n];
        int i=0;
        while(prev!=null){
            reverse[i]=prev.val;
            prev=prev.next;
            i++;
        }
        return reverse;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2022年11月21日上午12:30

class Solution:
    def printListFromTailToHead(self , listNode: ListNode) -> List[int]:
        s = []
        res = []
        # 正序输出链表到栈中
        while listNode:
            s.append(listNode.val)
            listNode = listNode.next
        # 输出栈中的元素到数组中
        while len(s):
            res.append(s[-1])
            s.pop()                 #倒着遍历且不断删除最后一个
        return res

0 赞同 0 条回复

PatNick 普通 2022年11月13日下午3:23

def reversePrint(head:ListNode)->list[int]:
    '''
    用栈（一般用list作为栈）：
    stack = []
    while head:
        stack.append(head.val)
        head = head.next
    return stack[::-1]
    '''

    '''
    递归：从用往左添加列表
    '''
    n = []
    cur = head
    count = 0
    while cur:
        count += 1
        cur = cur.next
    cur = head
    n = [0] * count
    while cur:
        count -= 1
        n[count] = cur.val
        cur = cur.next

    return n

0 赞同 0 条回复

Xiao 普通 2022年11月2日下午7:10

class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null)
            return new int[0];
            int i=0;
            ListNode p=head;
        while(p!=null){//先看看有多少元素
            i++;
            p=p.next;
        }
        int[] a= new int[i];
        for(int t=i-1;t>=0;t--){从尾部开始存放
            a[t]=head.val;
            head=head.next;
        }
        return a;
    }
}

0 赞同 0 条回复

小趴菜永久会员 2022年10月31日下午11:12

查长度，构造数组反向遍历输出
class Solution {
public int[] reversePrint(ListNode head) {
ListNode p1 = head;
int count = 0;
while(p1!=null){
p1 = p1.next;
count++;
}
int []nums = new int[count];
p1 = head;
for(int i =count-1;i>=0;i–){
nums[i] = p1.val;
p1 = p1.next;
}
return nums;

}

0 赞同 0 条回复

hmmm 普通 2022年10月30日下午10:18

“`c++“`
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector result = {};
void dfs(ListNode *head){
if(!head)
return;
dfs(head->next);
result.push_back(head->val);
}
vector reversePrint(ListNode* head) {
dfs(head);
return result;
}

};
递归法实现：
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

长青普通 2022年10月29日下午3:09

先查出链表长度，构建同长度数组，遍历链表给数组赋值

class Solution {
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;
}
}

0 赞同 0 条回复

叶页耶夜烨邺普通 2022年10月28日下午6:41

递归

/**
 * 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) {
        rec(head);
        return res;
    }

private:
    vector<int> res;

    void rec(ListNode* node){
        if(!node) return;
        rec(node->next);
        res.push_back(node->val);
    }
};

0 赞同 0 条回复

和普通 2022年10月28日下午1:04

public int[] reversePrint(ListNode head) {
        //遍历链表得出链表长度
        ListNode list=head;
        int size = 0;
        while (list!=null){
            size++;
            list=list.next;
        }
        //创建动态数组
        int[] arrayList=new int[size];
        //进行i--的遍历方法，使链表成倒序存放在数组中
        for (int i = size-1; i > -1 ; i--) {
            arrayList[i]=head.val;
            head=head.next;
        }
        return arrayList;
    }

0 赞同 0 条回复

-辰华- 永久会员 2022年10月27日上午12:23

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        // 栈：先进后出
        // 判断head是否为空，若为空，返回空数组
        if (head == null) return new int[0];
        Stack<ListNode> s = new Stack<ListNode>();
        // 入栈
        while (head != null) {
            s.push(head);
            head = head.next;
        }
        int[] res = new int[s.size()];
        // 出栈，放入数组中
        for (int i = 0; i < res.length; i++) {
            res[i] = s.pop().val;
        }
        return res;
    }
}

时间复杂度、空间复杂度均为：O(n)

0 赞同 0 条回复

lobort 普通 2022年10月26日下午9:54

class Solution {
    public int[] reversePrint(ListNode head) {
//方法一  从数组尾部添加
        if(head == null){
            return new int[0];
        }
        int count = 0;
        ListNode temp = head;
        while(temp!=null){
            temp = temp.next;
            count++;
        }
        int [] res = new int[count];
        int k = count -1;
        while(head!=null){
            res[k--] = head.val;
            head = head.next;
        }
        return res;

//方法二  利用栈先进后出的特性  
        Stack<Integer> st = new Stack<Integer>();
        int count = 0;
        while(head!=null){
            st.add(head.val);
            head = head.next;
        }
        int [] res = new int[st.size()];
        for(int i =0; i <res.length; i++){
            res[i] = st.pop();
        }
    return res;
    }
}

0 赞同 0 条回复

努力刷题普通 2022年10月26日上午1:53

栈
class Solution(object):
    def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        stack = []
        while head:
            stack.append(head.val)
            head = head.next
        return stack[::-1]

递归
class Solution(object):
    def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        if head:
            return self.reversePrint(head.next) + [head.val]
        return []

0 赞同 0 条回复

cxc 普通 2022年10月26日上午12:36

class Solution {
    List<Integer> list = new ArrayList();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] res = new int[list.size()];
        for(int i=0;i<res.length;i++){
            res[i] = list.get(i);
        }

        return res;
    }

    public void recur(ListNode head) {
        if(head == null) return;
        recur(head.next);
        //递归的时候添加到list头
        list.add(head.val);
    }
}

0 赞同 0 条回复

韩杰普通 2022年10月25日下午8:03

1,利用递归，递归到最后一个值然后添加到链表
2，时间复杂度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> 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 条回复

星河普通 2022年10月25日下午12:27

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);
    }
}
时间O(N)，空间O(N)

0 赞同 0 条回复

云雾里普通 2022年10月24日下午9:55

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
//递归
    public int[] reversePrint(ListNode head) {
       return digui(head,0);
    }
    private int[] digui(ListNode head,int sum){
        if(head==null){
            return new int[sum];
        }
        sum++;
        int[] ints  =digui(head.next,sum);
        if(ints!=null){
          int index =  ints.length-sum;
          ints[index]=head.val;
        }
        return ints;
    }
}

0 赞同 0 条回复

cute. 普通 2022年10月24日下午9:32

思路: 递归实现

var reversePrint = function(head) {
    if(head == null) {
        return [];
    }
    let result = reversePrint(head.next);
    result.push(head.val);
    return result
};

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

0 赞同 0 条回复

lone。普通 2022年10月24日下午9:19

解法一：递归

class Solution {
  public int[] reversePrint(ListNode head) {

      //若链表为null，返回空数组
      if (head == null) {
          return new int[0];
      }

      //使用集合填充链表值
      List temp = new ArrayList();
      //递归填充
      recur(head, temp);
      //遍历填充数组
      int[] array = new int[temp.size()];
      for (int i = 0; i < temp.size(); i++) {
          array[i] = (int) temp.get(i);
      }
      return array;
  }

  void recur (ListNode head, List temp) {
      if (head == null) {
          //结束递归
          return;
      } else {
          recur(head.next, temp);
      }
      //从后往前添加链表值
      temp.add(head.val);
  }
}

时间复杂度：O(N) 遍历链表，递归N次

空间复杂度：O(N) 使用O(N)的栈空间

解法二：栈

class Solution {
  public int[] reversePrint(ListNode head) {
      //若链表为null，返回空数组
      if (head == null) {
          return new int[0];
      }
      Stack<ListNode> stack = new Stack<>();
      while (head != null) {
          stack.push(head);
          head = head.next;
      }
      int size = stack.size();
      int[] array = new int[size];
      for (int i = 0; i < size; i++) {
          array[i] = stack.pop().val;
      }
      return array;
  }

}

时间复杂度：O(N) 入栈和出栈使用O(N)时间

空间复杂度：O(N)

0 赞同 0 条回复

云永久会员 2022年10月24日下午8:53

在想用遍历的方式让指针走到队尾，可是有个疑问，就算最后指向了末尾，要怎么取出上一个结点呢？？？
这个题有个特点–先进后出，利用数组，每次获取一个数就把他插入进去，这样遍历数组，读出来的顺序刚好就是相反的

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       ArrayList<Integer> list= new ArrayList<>();
       ListNode p1=listNode;
       while(p1!=null){
           list.add(0,p1.val);
           p1=p1.next;
       }
       return list;



    }
}

0 赞同 0 条回复

zjl 普通 2022年10月24日下午7:15

递归。但是list怎么能直接取出数组？

    public int[] reversePrint(ListNode head) {
        List list = new ArrayList();
        addNode(head,list);
        int[] arr = new int[list.size()];
        for(int i = 0 ; i < arr.length;i++){
            arr[i] = list.get(i);
        }
        return arr;

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

0 赞同 0 条回复

乱世枭雄普通 2022年10月24日下午7:05

思路：
只需要打印不需要反转，所以我们利用栈数据结构，先进后出。

class Solution {
    public int[] reversePrint(ListNode head) {
    Stack<ListNode> stk=new Stack<ListNode>();
    ListNode temp =head ;
    while(temp!=null){
        stk.push(temp);
        temp=temp.next;

    }
    int n=stk.size();
    int[] res=new int[n];
    for(int i=0;i<n;i++){
        res[i]=stk.pop().val;
    }
    return res;
    }
}

0 赞同 0 条回复

晨渊普通 2022年10月24日下午2:12

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        ListNode *temp = head;
        //先统计节点个数  再给Vector分配空间，size=0的话也可以
        int count=0;
        while(temp!=NULL){
            ++count;
            temp = temp->next;
        }
        vector<int> vec(count);
        if(count== 0)  return vec;

        temp = head;
//遍历链表，倒着存到数组
        for(int i= count-1;i>=0;--i){
            vec[i] = temp->val;
            temp = temp->next;
        }
        return vec;   
    }
};

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

0 赞同 0 条回复

虾仁猪心普通 2022年10月24日下午1:51

思路：利用栈的特性，先进后出。将链表中的值先存入栈中（借助LinkedList），然后弹出栈顶元素并存入数组中。
时间复杂度： O(n)
空间复杂度： O(n)

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

0 赞同 0 条回复

刺猬普通 2022年10月24日上午11:53

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

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

0 赞同 0 条回复

忆霁昕永久会员 2022年10月24日上午10:50

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

class Solution {
    private List<Integer> result = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        reverse(head);
        int[] temp = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            temp[i] = result.get(i);
        }
        return temp;
    }
    //反向打印链表
    private void reverse(ListNode p) {
        //递归结束条件
        if (p == null) {
            return;
        }
        //先打印以p.next为头节点的链表
        reverse(p.next);
        result.add(p.val);
    }
}

0 赞同 0 条回复

🚲南下普通 2022年10月24日上午10:38

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

class Solution {
public:
    vector reversePrint(ListNode* head) {
        int counter = 0; //之前忘记赋初值
        ListNode* pre = head;
        while(pre!=nullptr){
            counter++;
            pre = pre->next;
        }

        vector A(counter); //定义数组接收
        while(head!=nullptr){
            // A.push_back(head->val);
            A[counter-1] = head->val; //从后往前赋值
            head=head->next;
            counter--;
        }
        return A;

    }
};

0 赞同 0 条回复

@ 普通 2022年10月24日上午9:19

递归

class Solution {
    ArrayList<Integer> list = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        if(head == null) return null;

        reversePrint2(head);

        int[] res = list.stream().mapToInt(Integer::valueOf).toArray();

        return res;
    }

    public void reversePrint2(ListNode head) {
        if(head == null)
            return;

        reversePrint2(head.next);

        list.add(head.val);

        return;


    }

}

0 赞同 0 条回复

啊哈普通 2022年10月24日上午12:14

/**
 * 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> res;    //定义vector

        ListNode* cur = head;

        while(cur != NULL){     //压入容器
            res.push_back(cur->val);
            cur = cur -> next;
        }

        //反转
        reverse(res.begin(), res.end());

        return res;

    }
};

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

0 赞同 0 条回复

阿白普通 2022年10月24日上午12:14

1、在对与不对之间含糊不清，采用后序遍历递归法
2、时间复杂度O（n），空间复杂度O（n）

#include <vector>

struct ListNode
{
    ListNode* next;
    int val;

};

std::vector<int> temp;

void reversePrint(ListNode *nodeA)
{
    if (nodeA == nullptr)
        return;
    reversePrint(nodeA->next);
    temp.push_back(nodeA->val);
}

0 赞同 0 条回复

xye 普通 2022年10月23日下午11:38

func reversePrint(head *ListNode) []int {
    if head == nil {
        return nil
    }
    pre := head
    res := []int{}
    for pre != nil {
        res = append(res, pre.Val)
        pre = pre.Next
    }

    for i,j := 0,len(res)-1; i<j; {
        res[i], res[j] = res[j], res[i]
        i++
        j--
    }
    return res
}

以上顺序读取，数组反转

0 赞同 0 条回复

Magi 普通 2022年10月23日下午11:18

class Solution {
    public int[] reversePrint(ListNode head) {
//先判断特殊的情况，头节点为空
        if (head == null) {
            return new int[0];
        }

        //首先统计数组有多少个结点
        //创建临时变量,定义计数器
        int count = 0;
        ListNode listNode = head;
        while (listNode != null) {
            count++;
            listNode = listNode.next;
        }

        //new一个长度为count的数组，从右开始往左
        int[] temp = new int[count];
        while(head!=null)
        {
            temp[--count] = head.val;
            head = head.next;
        }
        return temp;
    }
    }

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

0 赞同 0 条回复

cxxz 普通 2022年10月23日下午11:17

先用栈实现了一下，翻转这种第一时间想到栈。主要复习一下stl的一些基本操作。

vector reversePrint(ListNode* head) {
        vector res;
        if (head == nullptr)
            return res;

        stack temp;
        ListNode *tnode = head;
        int length = 0;
        while (tnode != nullptr)
        {
            temp.push(tnode->val);
            tnode = tnode->next;
            length++;
        }
        while (temp.size() != 0)
        {
            res.push_back(temp.top());
            temp.pop();
        }
        return res;
    }

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

然后再用在leetcode题解中学到的递归实现，其使用java实现在递归到最后一个null的时候得到了所需开辟数组的长度，非常优雅（虽然vector中没用到，但是思路很棒）并且这种算法不要考虑head=nullptr，第一层递归的判断帮助完成了。

    vector res;
    vector reversePrint(ListNode* head) {
        solve(head);
        return res;
    }

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

时间复杂度O(n)
空间复杂度O(n)（函数调用栈和vector）

最后用在老师视频讲解中的思路，抛开传统遍历一定从左至右的思想，也可以在添加到数据结构中的顺序为从后至前。这里体现为每个元素直接插入到vector的开头。

vector reversePrint(ListNode* head){
        vector res;
        if (head == nullptr)
            return res;
        ListNode * temp = head;
        while (temp != nullptr)
        {
            res.insert(res.begin(), temp->val);
            temp = temp->next;
        }

        return res;
    }

时间复杂度O(n)
空间复杂度O(n)
虽然三种方法的时间空间复杂度都在一个量级，但是用了栈的时间最快。

0 赞同 0 条回复

庄重普通 2022年10月23日下午10:40

// 3.数组从后往前遍历，链表从前往后遍历，数组中数据会是链表从尾到头的顺序
//  拓展：二维数组，你甚至可以从后往前，也可以从左上，右下等任何位置开始
class Solution {
public:
    vector reversePrint(ListNode* head) {      
        //计算链表的长度
        int headlen = 0;
        ListNode* pTmp = head;
        for(;pTmp != NULL;){
            ++headlen;
            pTmp = pTmp->next;
        }

        vector arrRet(headlen,0);
        // vector arrRet;
        // arrRet.resize(headlen);
        //从后向前遍历数组的同时插入链表数据
        for(;headlen > 0; --headlen){
            arrRet[headlen-1] = head->val;
            head = head->next;
        }
        return arrRet;
    }
};
//时间复杂度O(n) n为链表长度
//空间复杂度O(n) vector的空间，n为链表长度


//  2.链表反转；
//      2-1.利用递归特性
//不知道有没有熟悉递归的同学，有没有办法能一个函数里，利用递归实现反转打印
//我是借助了一个reverseList函数，如果放到一个函数里有些捋不清逻辑
class Solution {
public:
    ListNode* reverseList(ListNode* head){
        if(head == NULL) return NULL;
        if(head->next == NULL) return head;
        
        //进行反转链表
        ListNode* pTmp = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        
        return pTmp;
    }

    vector reversePrint(ListNode* head) {
        vector arrRet(0);

        ListNode* pRev = reverseList(head);

        for(; pRev != NULL;){
            arrRet.push_back(pRev->val);
            pRev = pRev->next;
        }

        return arrRet;
    }
};
//时间复杂度O(n) n为链表长度
//空间复杂度O(n) n为链表长度，递归消耗空间n，vector消耗空间n

0 赞同 0 条回复

Gg 普通 2022年10月23日下午10:22

class Solution {
    public int[] reversePrint(ListNode head) {
        // 利用动态数组保存
        List<Integer> list = new ArrayList<>();
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
        int[] d = new int[list.size()];
        for(int i = 0;i<list.size();i++){
            d[i] = list.get(list.size()-1-i);
        }
        return d;
    }
}

0 赞同 0 条回复

symbol 普通 2022年10月23日下午9:35

func reversePrint(head *ListNode) []int {
    //递归实质就是一个栈
    if head == nil{
        return nil
    }
    return append(reversePrint(head.Next), head.Val)
}

递归的实质是一个栈

0 赞同 0 条回复

泡芙永久会员 2022年10月23日下午9:19

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

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

    int len = 0;
    int[] res;
    int cur = 0;
    void traverse(ListNode head) {
        if(head == null) {
            res = new int[len];
            return;
        }
        len ++;
        traverse(head.next);
        res[cur] = head.val;
        cur ++;
    }
}

0 赞同 0 条回复

T 普通 2022年10月23日下午7:59

下面是代码

class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null) 
            return new int[0];
        ListNode tmp = head;
        int len = 0;
        // 获得链表长度
        while(tmp != null) {
            len++;
            tmp = tmp.next;
        }
        int[] arr = new int[len];
        // 根据len， 倒叙插入value
        while(head != null) {
            arr[--len] = head.val;
            head = head.next;
        }
        return arr;
    }
}

0 赞同 0 条回复

Whatever 永久会员 2022年10月23日下午7:50

第一种：递归解决，类似二叉树后序遍历的思想（运行时长高了，似乎List转int[]数组影响性能）O(n)

class Solution {
    public int[] reversePrint(ListNode head) {
        List list = new ArrayList<>();
        reverse(head,list);
        Integer[] nums = list.toArray(new Integer[list.size()]);
        return Arrays.stream(nums).mapToInt(Integer::valueOf).toArray();
    }
    public void reverse(ListNode head,List list){
        if(head == null){
            return ;
        }
        reverse(head.next,list);
        list.add(head.val);
        return;
    }
}

第二种：直接分两次遍历，先计算出链表长度，再从尾到头填入数组 O(n)

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 赞同 0 条回复

Ruby🗽 普通 2022年10月23日下午7:02

class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode temp = head;
        ListNode newNode = null;
        while (temp != null){
            ListNode newNode1 = temp.next;
            temp.next = newNode;
            newNode = temp;
            temp = newNode1;
        }
        ArrayList<Integer> objects = new ArrayList<>();
        while (newNode != null){
            objects.add(newNode.val);
            newNode = newNode.next;
        }
        int[] res = objects.stream().mapToInt(Integer::intValue).toArray();
       return res;
    }
}

不是最优解，采用了头插法的思路，反转链表

0 赞同 0 条回复

酥合普通 2022年10月23日下午6:38

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        int count = 0;
        ListNode p = head;
        while(p != null){
            count++;
            p = p.next;
        }
        int[] ans = new int[count];
        p = head;
        for(int i = count - 1; i >= 0; i--) {
            ans[i] = p.val;
            p = p.next;
        }
        return ans;
    }
}

时间复杂度：O(n)

0 赞同 0 条回复

Error 普通 2022年10月23日下午6:32

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        n = []
        while head:
            n.insert(0, head.val)
            head = head.next
        return n

时间复杂度 O(n)

0 赞同 0 条回复

绍熙普通 2022年10月23日下午5:24

/*
        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 赞同 0 条回复

just 普通 2022年10月23日下午5:22

//recursion递归遍历
class Solution {
public:
vector res;
void fun(ListNode* head){
if(!head) return;
fun(head->next);
res.push_back(head->val);
return;;
}
vector reversePrint(ListNode* head) {
fun(head);
return res;

};

0 赞同 0 条回复

如梦似歌普通 2022年10月23日下午5:06

class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode p = head;
        int len = 0;
        //计算出链表的长度
        while(p != null){
            len++;
            p = p.next;
        }
        int[] a = new int[len];
        //因为数组最大下标恰好是链表的长度-1
        int k = len - 1;
        p = head;
        //从数组最大下标处开始为数组赋值
        while(p != null){
            a[k--] = p.val;
            p = p.next;
        }
        return a;
    }
}

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

0 赞同 0 条回复

Haoyun 普通 2022年10月23日下午4:20

var reversePrint = function(head) {
  if(!head) return [];
  let length = 0;
  let temp = head;
  while(temp) {
      length++;
      temp = temp.next;
  }
  let result = [];
  let k = length -1;
  while(length--) {
     result[k--] = head.val;
     head = head.next;
  }
  return result;
};

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

0 赞同 0 条回复

YZ 普通 2022年10月23日下午4:16

class Solution {
    public int[] reversePrint(ListNode head) {
        if(head==null)    //首先判断链表第一个结点(首元结点)是否为空，注意这里力扣将head作为了链表中的首元结点，这里的head是第一个结点，所以直接判断head是否为空，而不是head.next
        {
            return new int[0];
        }
        int count = 0;
        ListNode p = head;
        while(p!=null)   //将链表的长度计算出来，new出长度相对应的数组
        {
            count++;
            p = p.next;
        }
        p = head;
        int []result = new int[count];
        int k = count-1;
        for(;k>=0;k--)  //将数组从后往前记录链表中的val值，数组中最后一个存放链表中的第一个val值
        {
            result[k] = p.val;
            p = p.next;
        }
        return result;
        //感悟：以前学的都是理论知识，到实际操作错误很多，还需要多加练习
    }
}

时间复杂度：O(n)
空间复杂度：O(n)
C++的STL和Java中的关于栈的操作还不会，以后还要多加练习。

0 赞同 0 条回复

Chin 普通 2022年10月23日下午4:10

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

            Stack<Integer> stack = new Stack();
            ListNode cur = head;
            while (cur != null) {
                stack.push(cur.val);
                cur = cur.next;
            }

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

            for (int i = 0; i < result.length; i++) {
                result[i] = stack.pop();
            }
            return result;
        }
}

栈
时间复杂度On
空间复杂度On

0 赞同 0 条回复

追普通 2022年10月23日下午3:32

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        stack<int> stk;
        vector<int> vec;
        while(head != nullptr){
            stk.push(head->val);
            head = head->next;
        }
        while(!stk.empty()){
            vec.push_back(stk.top()); //取栈顶元素放到vector容器中
            stk.pop(); //将栈顶元素弹出栈
        }
        return vec;
    }
};

熟悉向vector容器中添加数，取栈顶元素以及将栈顶元素弹出栈的语法

0 赞同 0 条回复

是梦终空永久会员 2022年10月23日下午3:01

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

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

0 赞同 0 条回复

Tolkien 永久会员 2022年10月23日下午3:00

方法一：栈
1. 时间复杂度：O(n)
2. 空间复杂度：O(n)
3. 代码

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

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

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

        return results;
    }

方法二：数组倒序添加元素
1. 时间复杂度：O(n)
2. 空间复杂度：O(1)
3. 代码

public int[] reversePrint1(ListNode head) {
        // 1. 构造一个长度与链表长度相同的数组
        int count = 0;
        ListNode temp = head;
        while (temp != null) {
            temp = temp.next;
            count ++;
        }

        int[] results = new int[count];

        // 2. 遍历链表，从数组尾从右往左添加元素实现倒序
        while (head != null) {
            results[count-1] = head.val;
            head = head.next;
            count --;
        }

        return results;
    }

0 赞同 0 条回复

猫猫真可爱普通 2022年10月23日上午11:26

根据长度建数组，然后遍历往里放

class Solution {
    public int[] reversePrint(ListNode head) {
        int ListLength=0;
        ListNode q=head;
        while(q!=null){
            ListLength++;
            q=q.next;
        }

        int[] a=new int[ListLength];
        int index=0;
        while(head!=null){
            a[ListLength-1-index]=head.val;
            index++;
            head=head.next;
        }
        return a;
    }
}

0 赞同 0 条回复

派大星普通 2022年10月23日上午11:20

//使用递归来计算
//时间复杂度O(n)
//空间复杂度O(n)
public class Solution {
    public static int[] reversePrint(ListNode head){
        if(head==null){
            return new int[0];
        }
        ListNode temp = head;
        List<Integer> list = new ArrayList<>();
        reverse(temp,list);
        int[] res = list.stream().mapToInt(Integer::intValue).toArray();
        return res;

    }

    private static void reverse(ListNode temp,List<Integer> list ) {
        if(temp != null){
            reverse(temp.next,list);
            list.add(temp.val);
        }
    }

}

0 赞同 0 条回复

Asphyxia 普通 2022年10月23日上午11:20

用栈操作，递归也可以

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        stack<int> s;
        ListNode* cur = head;
        while(cur){
            s.push(cur->val);
            cur=cur->next;
        }
        vector<int> ret;
        while(!s.empty()){
            int e = s.top();
            ret.push_back(e);
            s.pop();
        }
        return ret;
    }
};

0 赞同 0 条回复

浅夏的无奈普通 2022年10月23日上午11:01

class Solution {
    int count;
    int i=0;
    int [] nums;
    public int[] reversePrint(ListNode head) {
        //获取节点个数
        count++;
       if(head==null){
            nums = new int[count-1];
            return nums;
        }
        //递归调用
        reversePrint(head.next);
        nums[i]=head.val;
        i++;
        return nums;
    }
}

0 赞同 0 条回复

潜行1 我是火车王！普通 2022年10月23日上午10:23

递归
时间 O(N)
空间 O(N)

func reversePrint(head *ListNode) []int {
        // 空切片暂时这么写
    resSlice := []int{}
    if head == nil {
        return resSlice
    }

    var recursion func(*ListNode)
    recursion = func (node *ListNode) {
        if node == nil {
            return
        }
        recursion(node.Next)
        resSlice = append(resSlice, node.Val)
    }
    recursion(head)
    return resSlice
}

0 赞同 0 条回复

mpweixin用户永久会员 2022年10月23日上午9:48

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

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

0 赞同 0 条回复

单个酒窝儿普通 2022年10月23日上午9:15

1、先准备一个vector和stack容器，如果头节点为空，则直接返回vector
2、再将链表中的节点压入栈中
3、最后将栈中的值取出放到vector中
时间复杂度O(n) 空间复杂度O(1)

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        stack<ListNode*> stc;
        vector<int> vec;
        if(head == NULL) return vec;

        while(head != NULL){
            stc.push(head);
            head = head->next;
        }

        while(!stc.empty()){
            ListNode* tmp = stc.top();
            stc.pop();
            vec.push_back(tmp->val);
        }
        return vec;
    }
};

0 赞同 0 条回复

糖香香普通 2022年10月23日上午2:33

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 条回复

Lyyyyh 普通 2022年10月23日上午2:11

//本题可以不额外使用容器，直接用数组，利用回溯算法，先得到数组总长度，再初始化数组，再回溯过程中，为数组赋值
class Solution {
int[] res;
int count;
public int[] reversePrint(ListNode head) {
process(head, 0);
return res;
}
void process(ListNode head, int i) {
if (head null) {
count = i;
res = new int[count];
return;
}
process(head.next, i + 1);
res[count – i – 1] = head.val;
}
}

0 赞同 0 条回复

yanshuojune 普通 2022年10月23日上午12:45

解体思路：递归
时间复杂度：O(n)
空间复杂度：O(n)

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        # 栈
        # stack = []
        # curr = head
        # while curr != None:
        #     stack.append(curr.val)
        #     curr = curr.next
        # return stack[::-1]

        # 递归
        curr = head
        if curr == None:
            return []
        return self.reversePrint(curr.next) + [head.val]

0 赞同 0 条回复

黎昕普通 2022年10月23日上午12:21

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

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

// 数组读出后前后依次交换
时间复杂度：O(n)
空间复杂度：O(1) // 数组本身不算

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int>arr;
        while(head!=NULL){
            arr.push_back(head->val);
            head=head->next;
        }
        for(int i=0;i<arr.size()/2;i++)
        {
            int tmp=arr[i];
            arr[i]=arr[arr.size()-1-i];
            arr[arr.size()-1-i]=tmp;
        }
        return arr;
    }
};

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月22日下午11:08

递归

//递归转换为数组
//时间复杂度 O(N)： 遍历链表，递归 N 次。
//空间复杂度 O(N)： 系统递归需要使用 O(N) 的栈空间。
class Solution {
    List<Integer> list = new ArrayList<>();
    int index = 0;
    public int[] reversePrint(ListNode head) {
        if(head == null) return new int[0];
         sort(head);
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
    public void sort(ListNode head){
        if(head != null && head.next != null) sort(head.next);
        list.add(head.val);
        return ;
    } 
}

//优化递归
class Solution {
    int start = 0;
    int end = 0;
    int[] ret;
    public int[] reversePrint(ListNode head) {
        if(head == null) return new int[0];
        sort(head);
        return ret;
    }
    public void sort(ListNode head){
        if(head == null){
            ret = new int[end];
            return ;
        }
        end++;
        sort(head.next);
        ret[start++] = head.val;
        return ;
    } 
}

简单做法

//简单做法：遍历一次获取长度，根据长度创建数组
//时间复杂度O(n)空间复杂度O(1)
class Solution {
    public int[] reversePrint(ListNode head) {
        int count = 0;
        ListNode cur = head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        int[] ret = new int[count];
        while(head != null){
            ret[--count] = head.val;
            head = head.next;
        }
        return ret;
    }
}

辅助栈

//辅助栈
//时间复杂度O(n) 空间复杂度O(n) ret和栈的空间为O(n)
class Solution {
    public int[] reversePrint(ListNode head) {
        LinkedList<Integer> stack = new LinkedList<>();
        while(head != null){
           stack.addLast(head.val);
           head = head.next;
        }
        int[] ret = new int[stack.size()];
        for(int i = 0;i < ret.length;i++){
            ret[i] = stack.removeLast();
        }
        return ret;
    }
}

0 赞同 0 条回复

马啸天永久会员 2022年10月22日下午10:34

public class Solution {

    public static void main(String[] args) {
        ListNode head = new ListNode(2);
        ListNode cur = head;
        cur.next = new ListNode(3);
        cur.next.next = new ListNode(5);
        int[] ints = new Solution().reversePrint(head);
        System.out.println(Arrays.toString(ints));
    }

    public int[] reversePrint(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode nex;
        int num = 0;
        while (cur != null) {
            nex = cur.next;
            cur.next = pre;
            pre = cur;
            num++;
            cur = nex;
        }

        //此时pre指向反向链表的头结点
        int[] nums = new int[num];
        for (int i = 0; i < num; i++) {
            if (pre != null) {
                nums[i] = pre.val;
                pre = pre.next;
            }
        }

        return nums;

    }
}

class Solution2 {

    public int[] reversePrint(ListNode head) {
        //可以使用栈
        LinkedList<Integer> stack = new LinkedList();
        int num = 0;
        while (head != null) {
            stack.push(head.val);
            num++;
            head = head.next;
        }

        int[] nums = new int[num];
        for (int i = 0; i < num; i++) {
            if (!stack.isEmpty())
                nums[i] = stack.pop();
        }
        return nums;
    }
}

class Solution3 {
    //递归
    LinkedList<Integer> linkedList = new LinkedList();

    public int[] reversePrint(ListNode head) {
        getValues(head);
        int [] nums=new int[linkedList.size()];
        for (int i = 0; i < linkedList.size(); i++) {
            nums[i]=linkedList.get(i);
        }
        return nums;

    }

    public void getValues(ListNode listNode) {
        if (listNode == null) {
            return;
        }
        getValues(listNode.next);
        linkedList.add(listNode.val);
    }
}

class Solution4{

    //先统计数，在倒着来计算
    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 条回复

晨普通 2022年10月22日下午10:05

class Solution(object):
    def reversePrint(self, head):
        # 判空
        if not head:
            return []
        li = []
        temp = head
        while temp:
            li.append(0)
            temp = temp.next
        for i in range(len(li)-1,-1,-1):
            li[i] = head.val
            head = head.next
        return li

0 赞同 0 条回复

溴麝香草酚蓝普通 2022年10月22日下午9:48

思路
1. 链表的倒序输出可以使用栈或者递归
2. 链表长度不定,先使用列表接收链表中的值,再将列表转换成数组返回
3. 先进入递归的下一层,再用列表接收链表中的值,列表的顺序即为链表的倒序,后续不用再做处理.
代码

class Solution {
    ArrayList<Integer> reslutArray = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        getValues(head);
        int[] values = new int[reslutArray.size()];
        for (int i = 0; i < values.length; i++) {
            values[i] = reslutArray.get(i);
        }
        return values;
    }

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

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

0 赞同 0 条回复

狗蛋儿普通 2022年10月22日下午9:41

直接利用栈的特性来可能是最简单，利用栈则可以使用递归的方法，这里暂时不给出.

复杂一点就是可以直接将链表反转，稍微复杂一些

时间复杂度和空间复杂度都为o(n)

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

0 赞同 0 条回复

宁永久会员 2022年10月22日下午9:34

递归解法

class Solution {
    LinkedList list = new LinkedList<>();
    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;
    }
    public void reverse(ListNode cur){
        if(cur == null)
            return;
        reverse(cur.next);
        list.add(cur.val);
    }
}

倒序填充

class Solution {  
    public int[] reversePrint(ListNode head) {
        ListNode cur = head;
        int length = 0;
        while(cur != null){
            length++;
            cur = cur.next;
        }
        cur = head;
        int[] res = new int[length];
        for(int i = length - 1; i >= 0; i --){
            res[i] = cur.val;
            cur = cur.next;
        }
        return res;
    }
}

利用栈的结构

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

0 赞同 0 条回复

波波_1936 普通 2022年10月22日下午9:31

    public int[] reversePrint(ListNode head) {
        if (head == null) {
            return new int[0];
        }
        //方法1 使用栈存储 然后出栈  时间复杂度O(n) 空间复杂度O(1)
       /* Stack<Integer> stack = new Stack<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for (int i = 0; i < stack.size(); i++) {
            res[i] = stack.pop();
        }
        return res;*/
        //方法2 先逆序饿然后打印，时间复杂度O(n) 空间复杂度也为O(n)  但是省了栈到空间

        ListNode pre = null;
        ListNode cu = head;
        int size = 0;//计算链表长度，用来初始化数组
        while (cu != null) {
            ListNode next = cu.next;
            cu.next = pre;
            pre = cu;
            cu = next;
            size++;
        }
        //反转后头节点是pre
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = pre.val;
            pre = pre.next;
        }
        return res;
    }

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

0 赞同 0 条回复

Spermalow 普通 2022年10月22日下午9:29

class Solution {
public:
    vector reversePrint(ListNode* head) {
        vector res;
        if (!head) return {0};
        while (head) {
            res.push_back(head->val);
            head = head->next;
        }
        // STL常用库函数，可以将一个vector翻转
        reverse(res.begin(), res.end());
        return res;
    }
};

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

0 赞同 0 条回复

mpweixin用户普通 2022年10月22日下午9:13

// 用栈存储节点的值，遍历完链表后出栈
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> s = new Stack<>();
        while(head != null){
            s.push(head.val);
            head = head.next;
        }
        int len = s.size();
        int[] res = new int[len];
        for(int i = 0; i < len; i++)
            res[i] = s.pop();
        return res;
    }
}

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

0 赞同 0 条回复

你有点可爱喔普通 2022年10月22日下午9:13

解题思路：
1.辅助结点cur,进行遍历计数，计算出链表的长度
2.给出一个数组数组的长度为链表的长度
3.初始化结点，反向遍历输出值，将其赋值给好的数组中

 public int[] reversePrint(ListNode head) {
            ListNode cur = head;
            int count = 0;
            while(cur!=null){
                cur = cur.next;
                count++;
            }
            int arr [] = new int[count];
            //重新初始辅助结点
            cur = head;
            while(cur!=null){
                arr[--count] = cur.val;
                cur = cur.next;
            }
            return arr;
    }

1 赞同 0 条回复

鸿渐普通 2022年10月22日下午9:11

class Solution {
    public int[] reversePrint(ListNode head) {
       //利用栈的特性解决这个问题
        Deque<Integer> integerDeque = new ArrayDeque<>();

        //开始遍历链表，将链表的值全部放到栈当中去
        while (head!=null){
            integerDeque.push(head.val);
            head=head.next;
        }

        int[] res = new int[integerDeque.size()];
        int index = 0;
        while (!integerDeque.isEmpty()){
            res[index]=integerDeque.pop();
            index++;
        }
        return res;
    }
}

0 赞同 0 条回复

易水寒永久会员 2022年10月22日下午9:06

递归

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

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

0 赞同 0 条回复

王艺超普通 2022年10月22日下午8:58

利用栈结构就可以实现

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

    }
};

0 赞同 0 条回复

小肸永久会员 2022年10月22日下午8:21

思路一：翻转链表并从头节点开始存数据到数组中，时间复杂度O(N)，空间复杂度O(N)。
思路二：先遍历一遍链表确定数组长度，然后从头节点和数组默认开始存数据。时间复杂度O(N)，空间复杂度O(N)。
思路三：适合用递归实现，因为是从尾开始打印，就是说先访问到的数据后打印，栈的特性，可以借助栈来实现，递归的本质也是栈。时间复杂度O(N)，空间复杂度O(N)。
给出递归实现

class Solution {
    private List<Integer> temp = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        reversePrintCore(head);
        int[] res = new int[temp.size()];
        for (int i = 0; i < temp.size(); i ++) {
            res[i] = temp.get(i);
        }
        return res;
    }
    private void reversePrintCore(ListNode head) {
        if (head == null) {
            return;
        }
        reversePrintCore(head.next);
        temp.add(head.val);
    }
}

0 赞同 0 条回复

青木普通 2022年10月22日下午8:20

/*
刚开始写java，不太会，看了题解，使用列表保存数据再转换成int[]
*/
class Solution {
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] ans = new int[tmp.size()];

        for(int i=0; i<ans.length; i++){
            ans[i] = tmp.get(i);
        }
        return ans;

    }
    void recur(ListNode head){
        if(head == null) return;
        recur(head.next);
        tmp.add(head.val);
    }
}
//时间复杂度：O(n)
//空间复杂度：O(n)


/*
有了链表就好写栈方法了
*/
class Solution {
    public int[] reversePrint(ListNode head) {
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        while(head != null){
            tmp.add(head.val);
            head = head.next;
        }
        int[] ans = new int[tmp.size()];
        for(int i=0; i<ans.length; i++){
            ans[i] = tmp.get(ans.length-1-i);
        }
        return ans;
    }
}
//时间复杂度：O(n)
//空间复杂度：O(n)

0 赞同 0 条回复

So 普通 2022年10月22日下午8:14

第二天第一题

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

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

0 赞同 0 条回复

一只骆驼普通 2022年10月22日下午8:02

先遍历一次链表确定链表长度，再遍历一次存入数组
时间空间都是O(n)

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

0 赞同 0 条回复

1ue1uekin8 普通 2022年10月22日下午7:42

都是O(n)

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 条回复

天然普通 2022年10月22日下午7:36

时间和空间复杂度都为O(n)

class Solution(object):
    def reversePrint(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """

        lst =[]

        while head != None:
            lst.append(head.val)
            head = head.next



        for i in range(len(lst)//2):
            temp = lst[i]
            lst[i] = lst[-(i+1)]
            lst[-(i+1)] = temp

        return lst

0 赞同 0 条回复

wxc 普通 2022年10月22日下午7:28

额

class Solution(object):
    def reversePrint(self, head):
        return self.reversePrint(head.next) + [head.val] if head else []

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月22日下午7:13

方法一：时间空间复杂度都为O（n)

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> s = new Stack<>();
        int count = 0;
        while(head!=null){
            s.push(head.val);
            count++;
            head = head.next;
        }
        int[] in = new int[count];
        for(int i=0;i<count;i++){
            in[i] = s.pop();

        }
        return in;

    }
}

方法二：递归

class Solution {
    int count;
    int count1;
    int[] res;
    public int[] reversePrint(ListNode head) {
        if(head==null){
            res = new int[count];
            return res;
        }
        count++;
        reversePrint(head.next);
        res[count1] = head.val;
        count1++;
        return res;
    }
}

0 赞同 0 条回复

Y7n05h 普通 2022年10月22日下午7:05

class Solution {
    void process(vector<int> &res, ListNode *node) {
        if (!node) {
            return;
        }
        process(res, node->next);
        res.push_back(node->val);
    }

public:
    vector<int> reversePrint(ListNode *head) {
        vector<int> res;
        process(res, head);
        return res;
    }
}

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

0 赞同 0 条回复

194分贝普通 2022年10月22日下午6:44

class Solution {
  public:
    vector printListFromTailToHead(ListNode* head) {

        // 统计链表长度
        int k = -1;
        ListNode* pNode = head;
        while (pNode) {
            k++;
            pNode = pNode->next;
        }

        // 由后往前存入数组
        vector ivec(k+1);
        pNode = head;
        while (pNode) {
            ivec[k--] = pNode->val;
            pNode = pNode->next;
        }

        return ivec;
    }
};

0 赞同 0 条回复

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

共以下 86 个回答

递归法

栈

先查出链表长度，构建同长度数组，遍历链表给数组赋值

直接利用栈的特性来可能是最简单，利用栈则可以使用递归的方法，这里暂时不给出.

复杂一点就是可以直接将链表反转，稍微复杂一些

时间复杂度和空间复杂度都为o(n)

# 回答此问题取消回复

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

共以下 86 个回答

递归法

栈

先查出链表长度，构建同长度数组，遍历链表给数组赋值

直接利用栈的特性来可能是最简单，利用栈则可以使用递归的方法，这里暂时不给出.

复杂一点就是可以直接将链表反转，稍微复杂一些

时间复杂度和空间复杂度都为o(n)

# 回答此问题 取消回复

# 回答此问题取消回复