跳转至

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

问题描述#

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

 

示例 1：

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

 

限制：

0 <= 链表长度 <= 10000

解题思路#

可以先将链表逆序，也可以获取元素后将数组逆序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        # 逆序链表
        vhead = ListNode(0)
        p = head
        while p:
            q = p.next
            p.next = vhead.next
            vhead.next = p
            p = q

        p = vhead.next
        ans = []
        while p:
            ans.append(p.val)
            p = p.next

        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        // 逆序数组
        vector<int> ans;
        auto p = head;
        while (p) {
            ans.emplace_back(p->val);
            p = p->next;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

时间复杂度：\(\mathcal{O}(n)\)
空间复杂度：\(\mathcal{O}(n)\)

返回顶部

在手机上阅读