题目

输入一个单链表链表的头结点，从尾到头打印每个节点的值。
题目很简单但是实现方法却可以有很多种，也能考察人的不同方面的知识。这里实现使用 go 语言。

实现

节点定义

首先说明这里不能使用各语言内置的链表，比如 java 的 LinkedList。这里要求的单链表只能有两个属性不能有其他的属性和方法。 go 语言定义如下

type ListNode struct {
    Val  int
    Next *ListNode
}

堆栈 or 数组

看到这个题目最先想到的就是用堆栈或数组来做，方法就是遍历所有节点放入到数组或堆栈然后再遍历打印。数组就比较简单了，这里写下堆栈的实现。 首先 go 里没堆栈先定义一个堆栈。

type myHeap []*ListNode

func (h *myHeap) Less(i, j int) bool {
    return (*h)[i].Val < (*h)[j].Val
}

func (h *myHeap) Swap(i, j int) {
    (*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *myHeap) Len() int {
    return len(*h)
}

func (h *myHeap) Pop() (v interface{}) {
    *h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1]
    return
}

func (h *myHeap) Push(v interface{}) {
    *h = append(*h, v.(*ListNode))
}

基于堆栈的实现

// 堆栈打印
func ReversePrintListNodeHeap(header *ListNode)  {
    heap := new(myHeap)
    // 遍历节点入栈
    for header != nil {
        heap.Push(header)
        header = header.Next
    }
    // pop 堆栈打印
    for heap.Len() > 0 {
        cur := heap.Pop()
        node := cur.(*ListNode)
        fmt.Println(node.Val)
    }
}

说到堆栈然后就可以顺势说下堆栈、队列相关概念和语言的具体实现等。

递归

说到堆栈就能想到递归，递归实现如下

// 递归打印
func ReversePrintListNodeRecursion(header *ListNode) {
    if header == nil {
        return
    }

    ReversePrintListNodeRecursion(header.Next)
    fmt.Println(header.Val)
}

说到递归可以问下语言最大调用堆栈的限制

遍历打印

遍历打印最简单的是先遍历一遍算出最大长度 n，再循环遍历打印第 n 个，第 n - 1 个…，这种比较简单，也可以使用如下的方法打印。

// 循环遍历打印
func ReversePrintListNodeTraverse(header *ListNode) {
    var last *ListNode
    for cur := header; last != header; cur = header {
        for cur.Next != last {
            cur = cur.Next
        }
        fmt.Println(cur.Val)
        last = cur
    }
}

循环反转打印

// 先反转再打印
func ReversePrintListNodeReverse(header *ListNode) {
    var pre *ListNode
    if header == nil {
        return
    }
    next := header.Next
    for next != nil {
        header.Next = pre
        pre = header
        header = next
        next = next.Next
    }
    header.Next = pre

    for header != nil {
        fmt.Println(header.Val)
        header = header.Next
    }
}

递归反转打印

// 递归反转打印
func ReversePrintListNodeRecursionReverse(header *ListNode) {
    header = recursionReverse(nil, header)

    for header != nil {
        fmt.Println(header.Val)
        header = header.Next
    }
}

func recursionReverse(pre, header *ListNode) *ListNode {
    if header == nil {
        return pre
    }
    next := header.Next
    header.Next = pre

    return recursionReverse(header, next)
}

总结

源码可参考
打印算法
测试代码