Go算法面试题：从尾到头打印链表

题目：从尾到头打印链表

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

示例：

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

限制：

0 <= 链表长度 <= 10000

解法1：递归法

因为是从尾到头返回每一个节点的值，所以很容易想到如果从最后的节点将值放入数组中，然后再往前逐步将数据放入数组，最后回到头节点返回即可，可以想到递归就能轻松做到，只要注意递归函数的结束条件即可。

<code>/**
* Definition for singly-linked list.
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func reversePrint(head *ListNode) []int {
   if head == nil {
       return nil
  }
   return appendData(head)
}
func appendData(head *ListNode) []int {
   if head.Next != nil{
       list := appendData(head.Next)
       list = append(list, head.Val)
       return list
  }
   return []int{head.Val}
}/<code>

自然而然，效率不会很高~

反思了一下，其实递归还可以再简短一点

<code>/**
* Definition for singly-linked list.
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func reversePrint(head *ListNode) []int {
   if head == nil {
       return []int{}
  }
   return append(reversePrint(head.Next), head.Val)
}/<code>

结果如下：

解法2：反转链表

想了一下，这样不行啊，耗时这么长，试试不用递归吧~如果我反转链表，再生成数组返回，这样也可以实现吧？

<code>/**
* Definition for singly-linked list.
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func reversePrint(head *ListNode) []int {
   if head == nil {
       return nil
  }
   var newHead *ListNode
   res := []int{}
   for head != nil {
       node := head.Next
       head.Next = newHead
       newHead = head
       head = node
  }
   for newHead != nil {
       res = append(res, newHead.Val)
       newHead = newHead.Next
  }
   return res
}/<code>

结果如下，好像没这么耗内存了：

解法3：反转数组

反转链表再获取数值，可以是可以，但会不会有点多余？不如试试直接顺序获取值放到数组，再反转结果呢？

<code>/**
* Definition for singly-linked list.
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func reversePrint(head *ListNode) []int {
   if head == nil {
       return nil
  }
   res := []int{}
   for head != nil {
       res = append(res, head.Val)
       head = head.Next
  }
   for i, j := 0, len(res)-1; i /<code>

至此，性能有了明显的提升：

解法4：栈

这个反转数组还是感觉好奇怪，有没有更好的方法呢？把先读到的放最后，最后的在最前面，栈不就是这样的数据结构吗？

<code>/**
* Definition for singly-linked list.
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
import "container/list"
func reversePrint(head *ListNode) []int {
   if head == nil {
       return nil
  }
   res := list.New()
   for head != nil {
       res.PushFront(head.Val)
       head = head.Next
  }
   ret := []int{}
   for e := res.Front(); e != nil; e = e.Next() {
       ret = append(ret, e.Value.(int))
  }
   return ret
}/<code>

三下五除二，搞定！来看看成果：

解法5：两次遍历

其实写完栈的解法，我以为这题就这样了，然而......

<code>/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {
    if head == nil {
        return nil
    }
    count := 0
    newHead := head
    for head != nil {
        count++
        head = head.Next
    }
    res := make([]int, count)
    i := 0
    for newHead != nil {
        res[count-i-1] = newHead.Val
        i++
        newHead = newHead.Next 
    }
    return res
}/<code>

卧槽！！！质的提升，既省去自动扩容的性能，也能提高处理速度：

欢迎留言一起探讨~