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

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

题目描述

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

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

解题思路

法1

递归
一个较容易想到 的方法,先递归到链表的尾部,再逐个递归返回,前面的返回值要append后面的返回值实现,链表的逆序输出

//核心递归代码
//
return append(reversePrint(head.Next), head.Val)

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

栈

1. 创建一个空的栈。
2. 遍历链表的所有元素，将每个元素入栈。
3. 创建一个空的数组，从栈中取出每个元素并添加到数组中。
4. 返回数组，数组中的元素即为链表的元素从后往前输出的顺序

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

执行结果

法1

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

执行用时： 4 ms , 在所有 Go 提交中击败了 57.53% 的用户 内存消耗： 4.5 MB , 在所有 Go 提交中击败了 29.89% 的用户

法2

func reversePrint(head *ListNode) []int {
    s := []int{}
    for head != nil {
        s = append(s, head.Val)
        head = head.Next
    }
    r:= make([]int, len(s))
    for i:=len(s)-1;i>=0;i-- {
        r[i]=s[len(s)-i-1]
    }
    return r
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 3 MB , 在所有 Go 提交中击败了 55.49% 的用户 通过测试用例： 24 / 24