06.从尾到头打印链表

题目描述 #

题目地址

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

示例 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