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

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

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

递归后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var res []int

func reversePrint(head *ListNode) []int {
    res = make([]int, 0)
    traverse(head)
    return res
}

func traverse(head *ListNode) {
    if head == nil {
        return
    }
    traverse(head.Next)
    res = append(res, head.Val)
}

两次遍历（实际运行更快，复杂度一样）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func reversePrint(head *ListNode) []int {
    count := 0
    p := head
    for p != nil {
        p = p.Next
        count++
    }

    res := make([]int, count)
    for i := count - 1; i >= 0; i-- {
        res[i] = head.Val
        head = head.Next
    }
    
    return res
}