免费网站在线制作,湖州建设局新网站,公司做网站多少钱,网站建设合同约定三年后题目 输入一个链表的头节点#xff0c;从尾到头反过来返回每个节点的值#xff08;用数组返回#xff09;。
示例 1#xff1a; 输入#xff1a;head [1,3,2] 输出#xff1a;[2,3,1]
限制#xff1a; 0 链表长度 10000
解法一#xff1a;递归#xff0…题目 输入一个链表的头节点从尾到头反过来返回每个节点的值用数组返回。
示例 1 输入head [1,3,2] 输出[2,3,1]
限制 0 链表长度 10000
解法一递归递归本来就是一种栈所以算做一类
func reversePrint(head *ListNode) []int {if head nil {return []int{}}if head.Next nil {return []int{head.Val}}return append(reversePrint(head.Next), head.Val)
}解法二逆置链表
func reversePrint(head *ListNode) []int {if head nil {return []int{}}// 逆置链表fistNode, mindNode : head, head.NextfistNode.Next nilfor {if mindNode nil {break}endNode : mindNode.NextmindNode.Next fistNodefistNode mindNodemindNode endNode}vals : make([]int,0)for {if fistNode nil {return vals}vals append(vals, fistNode.Val)fistNode fistNode.Next}
}解法三头部动态插入模拟切片动态扩容
func reversePrint(head *ListNode) []int {if head nil {return []int{}}vals : make([]int, 4)endIndex : len(vals)for {endIndex--if head nil {break}vals[endIndex] head.Valif endIndex 0 {vals, endIndex dilatation(vals)}head head.Next}return vals[endIndex1:]
}func dilatation(arr []int) ([]int, int) {lenArr : len(arr)restfulSize : lenArr lenArr/2restful : make([]int, restfulSize)endIndex : len(restful)arrIndex : lenArr - 1for {if arrIndex 0 {break}endIndex--restful[endIndex] arr[arrIndex]arrIndex--}return restful, endIndex
}总结可以看出头部动态插入与逆置链表再执行速度相同的情况下占用的空间还是比递归少一些虽然不是官方解法。
