of006.md

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

OF6.从尾到头打印链表

题目描述

题目地址

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

示例 1：

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

题解

思路1 ： 递归

递归遍历

算法流程：

1. 复杂度分析：
2. 时间复杂度$$O(N)$$**：**遍历N次，递归 N 次
3. 空间复杂度$$O(N)$$**：**递归 N 次，开辟 N 个栈空间

代码

{% tabs %} {% tab title="Go" %}

func reversePrint(head *ListNode) []int {
    ans := make([]int, 0)
    if head == nil {
        return ans
    }
    ans = reversePrint(head.Next)
    ans = append(ans, head.Val)
    return ans
}

{% endtab %} {% endtabs %}

思路1 ： 多指针

多个指针辅助，一次遍历

算法流程：

1. 复杂度分析：
2. 时间复杂度$$O(N)$$**：**遍历N次，递归 N 次
3. 空间复杂度$$O(N)$$**：**递归 N 次，开辟 N 个栈空间

代码

{% tabs %} {% tab title="Go" %}

func reversePrint(head *ListNode) []int {
    if head == nil {
        return []int{}
    }
    pre, cur, next, ans := &ListNode{}, head, head.Next, []int{}
    for cur != nil {
        next = cur.Next
        cur.Next = pre

        pre = cur
        cur = next
    }
    for pre.Next != nil {
        ans = append(ans, pre.Val)
        pre = pre.Next
    }
    return ans
}

{% endtab %} {% endtabs %}

总结

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 算法 题解：awesome-golang-algorithm