面试:从尾到头打印链表
2012 年 9 月 26 日
题目:从尾到头打印链表
要求:输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
示例:
输入: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} }
自然而然,效率不会很高~
反思了一下,其实递归还可以再简短一点
/** * 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) }
结果如下:
题解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 }
结果如下:
解法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 }
至此,结果有了很大的提升:
解法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 }
三下五除二,搞定!来看看成果:
解法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 }
卧槽!!!质的提升,既省去自动扩容的性能,也能提高处理速度:
欢迎关注公众号:若鱼治水,文章会首发在公众号,也可备注加我备注进群进技术交流群~