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

Leetcode 刷题

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

• 难度：简单

题目

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例1

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

提示

• 0 <= 链表长度 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

反转

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

复杂度

• 时间复杂度： 遍历了一遍数组，O(n)
• 空间复杂度： 使用了额外的result，O(n)

扩展

vector文档

vector成员函数

• 修改

  函数名	功能	类型
  clear	清除内容	(公开成员函数)
  insert	插入元素	(公开成员函数)
  emplace(C++11)	原位构造元素	(公开成员函数)
  erase	擦除元素	(公开成员函数)
  push_back	将元素添加到容器末尾	(公开成员函数)
  emplace_back(C++11)	在容器末尾就地构造元素	(公开成员函数)
  pop_back	移除末尾元素	(公开成员函数)
  resize	改变容器中可存储元素的个数	(公开成员函数)
  swap	交换内容	(公开成员函数)

思路

1. 调用vector的成员函数push_back将元素添加到容器末尾
2. 使用reverse(begin, end)进行反转

递归

class Solution {
public:
    vector<int> result;
    vector<int> reversePrint(ListNode* head) {
        // 终止条件
        if(!head){
            return result;
        }
        reversePrint(head -> next);
        result.push_back(head -> val);
        return result;

    }
};

复杂度

• 时间复杂度： 递归n次，时间复杂度O(n)，递归函数中时间复杂度O(1)，总时间复杂度O(n)
• 空间复杂度： O(n)

思路

1. 递归终止条件为head为空
2. 每head.next一次，进入reversePrint的数据长度就少了1

堆栈

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

复杂度

• 时间复杂度： push时间复杂度O(n) 、pop时间复杂度O(n)，总时间复杂度O(n)
• 空间复杂度： 使用了额外的result和堆栈，O(n)

思路

1. 利用堆栈先进后出的特点，先依次将元素压入堆栈中，然后将所有元素从堆栈中弹出，即可实现反转

三种方法资源消耗对比