面试:从尾到头打印链表

题目:从尾到头打印链表

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

示例:

输入: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

欢迎关注公众号:若鱼治水,文章会首发在公众号,也可备注加我备注进群进技术交流群~

本文来自:Segmentfault

感谢作者:若鱼治水

查看原文:面试:从尾到头打印链表

• 编辑
• 预览