剑指 Offer 06. 从尾到头打印链表

本问题对应的 leetcode 原文链接:剑指 Offer 06. 从尾到头打印链表
本文对应打卡链接:【链表专题】剑指 Offer 06. 从尾到头打印链表

问题描述

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
示例 1:

输入:head = [1,3,2]
输出:[2,3,1]

限制:

0 <= 链表长度 <= 10000

解题思路

视频讲解直达: 本题视频讲解

代码实现

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

发表回复

后才能评论

评论(7)

  • 杨帆 普通 2022年11月1日 下午4:29

    public int[] reversePrint(ListNode head) {
    int len = 0;
    ListNode cur = head;
    while(cur != null){
    cur = cur.next;
    len++;
    }
    int[] a = new int[len];
    int num = 1;
    cur = head;
    while(cur != null){
    a[len-num] = cur.val;
    num++;
    cur = cur.next;
    }
    return a;
    }

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

  • lobort 普通 2022年10月26日 下午7:06
    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.add()增加元素 stack.pop()弹出栈内最上面的元素
    Stack st = new Stack();
    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;
    }
    }
    
  • lobort 普通 2022年10月26日 下午7:05

    “`java
    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.add()增加元素 stack.pop()弹出栈内最上面的元素
    Stack st = new Stack();
    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;
    }
    }

  • cxc 普通 2022年10月24日 下午11:55
    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);
        }
    }
    
  • zjl 普通 2022年10月24日 下午7:14

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

        public int[] reversePrint(ListNode head) {
            List<Integer> 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<Integer> list){
            if(node==null){
                return;
            }
            addNode(node.next,list);
            list.add(node.val);
        }
    
  • 🚲南下 普通 2022年10月24日 上午10:37

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

    class Solution {
    public:
        vector<int> reversePrint(ListNode* head) {
            int counter = 0; //之前忘记赋初值
            ListNode* pre = head;
            while(pre!=nullptr){
                counter++;
                pre = pre->next;
            }
    
            vector<int> A(counter); //定义数组接收
            while(head!=nullptr){
                // A.push_back(head->val);
                A[counter-1] = head->val; //从后往前赋值
                head=head->next;
                counter--;
            }
            return A;
    
        }
    };
    
  • Edison 普通 2022年10月23日 下午9:32

    思路一:先反转链表,再遍历,这样就不需要额外的栈空间开销

    class Solution {
    public:
        vector<int> reversePrint(ListNode* head) {
            //先反转链表,再遍历,这样就不需要额外的栈空间开销
            vector<int> ret;
    
            // 空链表
            if (head == nullptr) {
                return ret;
            }
    
            // 反转链表
            ListNode* cur = head->next;
            ListNode* temp;
            head->next = nullptr;
            while (cur) { // 遍历链表
                temp = cur->next;
                cur->next = head;
                head = cur;
                cur = temp;
            }
    
            // 直接尾插
            while (head) {
                ret.push_back(head->val);
                head = head->next;
            }
            // 返回ret数组
            return ret;
        }
    };
    

    方法二:使用栈

    class Solution {
    public:
        vector<int> reversePrint(ListNode* head) {
            vector<int> ret;
            stack<int> st;
            while (head) {
                st.push(head->val); //把链表元素全部放入栈中
                head = head->next;
            }
            while (!st.empty()) {
                ret.push_back(st.top()); // 把栈顶元素放到ret数组中
                st.pop();
            }
            return ret;
        }
    };
    

    方法三:就地逆序数组

    class Solution {
    public:
        vector<int> reversePrint(ListNode* head) {
            vector<int> ret;
    
            // 把链表所有元素尾插到ret数组中
            while (head) {
                ret.push_back(head->val);
                head = head->next;
            }
            int len = ret.size(); //统计元素个数
    
            // 交换第一个和最后一个,只需要交换len/2次
            for (int i = 0; i < len / 2; ++i) {
                swap(ret[i], ret[len-i-1]);
            }
            return ret;
        }
    };