题目：从尾到头打印链表
要求：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例：
输入：head = [1,3,2] 输出：[2,3,1]限制：
0 <= 链表长度 <= 10000
题解1：递归法
因为是从尾到头返回每一个节点的值，所以很容易想到如果从最后的节点将值放入数组中，然后再往前逐步将数据放入数组，最后回到头节点返回即可，可以想到递归就能轻松做到，只要注意递归函数的结束条件即可。
/**
* 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}
}
自然而然，效率不会很高~
file
反思了一下，其实递归还可以再简短一点
/**
* 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)
}
结果如下：
file
题解2：反转链表
想了一下，这样不行啊，耗时这么长，试试不用递归吧~
然后就想，如果我反转链表呢，再生成数组返回，这样也可以实现吧？
/**
* 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
}
结果如下：
file
解法3：反转数组
反转链表再获取数值，可以是可以，会不会有点多余？还不如直接顺序获取值放到数组，再反转结果呢~
/**
* 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 < j; {
res[i], res[j] = res[j], res[i]
i++
j--
}
return res
}
至此，结果有了很大的提升：
file
解法4：栈
这个反转数组还是感觉好奇怪，有没有更好的方法呢？把先读到的放最后，最后的在最前面，栈不就是这样的数据结构吗？
/**
* 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
}
三下五除二，搞定！来看看成果：
file
解法5：遍历两次
其实到栈，我以为这题就这样了，然而......
/**
* 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
}
卧槽！！！质的提升，既省去自动扩容的性能，也能提高处理速度：
file
欢迎关注公众号：若鱼治水，文章会首发在公众号，也可备注加我备注进群进技术交流群~
