商标注册查询官网中国商标网,南京百度网站快速优化,网站标题一样,四川品牌网站建设目录
题目#xff1a;合并k个已排序的链表_牛客题霸_牛客网 (nowcoder.com)
题目的接口#xff1a;
解题思路#xff1a;
代码#xff1a;
过啦#xff01;#xff01;#xff01;
题目#xff1a;判断链表中是否有环_牛客题霸_牛客网 (nowcoder.com)
题目的接口…目录
题目合并k个已排序的链表_牛客题霸_牛客网 (nowcoder.com)
题目的接口
解题思路
代码
过啦
题目判断链表中是否有环_牛客题霸_牛客网 (nowcoder.com)
题目的接口
解题思路
代码
过啦
写在最后 题目合并k个已排序的链表_牛客题霸_牛客网 (nowcoder.com) 题目的接口
package main
import . nc_tools
/** type ListNode struct{* Val int* Next *ListNode* }*//*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param lists ListNode类一维数组 * return ListNode类
*/
func mergeKLists( lists []*ListNode ) *ListNode {// write code here
}
解题思路
这道题合并链表的部分和昨天的一模一样直接实现一个合并的方法调用就好了这道题目的核心思想是分治思想利用分治思想将所有链表合并具体操作如下
1当链表数量 0 时证明没有链表需要合并返回 nil
2当链表数量 1 时证明只剩一个链表了直接返回唯一的这一条链表
3当链表数量 2 时证明只剩下两条链表了返回这两个链表的合并
4当链表数量 2 时我们就利用分治的思想把这些链表对半分开计算一直递归分治直到链表的数量 2这样就可以走我们上面三条逻辑完成每一个部分的链表合并。代码如下
代码
package main
import . nc_tools
/** type ListNode struct{* Val int* Next *ListNode* }*//*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param lists ListNode类一维数组 * return ListNode类
*/
func mergeKLists( lists []*ListNode ) *ListNode {n : len(lists)if n 0 {return nil}if n 1 {return lists[0]}if n 2 {return merge(lists[0], lists[1])} tmp : n / 2return merge(mergeKLists(lists[:tmp]), mergeKLists(lists[tmp:]))}func merge(list1 *ListNode, list2 *ListNode) *ListNode {if list1 nil list2 nil {return nil}head : ListNode{}cur : headfor list1 ! nil list2 ! nil {if list1.Val list2.Val {cur.Next list1list1 list1.Next} else {cur.Next list2list2 list2.Next}cur cur.Next}if list1 ! nil {cur.Next list1}if list2 ! nil {cur.Next list2}return head.Next
}过啦 题目判断链表中是否有环_牛客题霸_牛客网 (nowcoder.com) 题目的接口
package main
import . nc_tools
/** type ListNode struct{* Val int* Next *ListNode* }*//*** * param head ListNode类 * return bool布尔型
*/
func hasCycle( head *ListNode ) bool {// write code here
}
解题思路
这道题非常非常的经典我也做过很多很多遍了我到现在还记得我第一次做这道题的时候的思路我当时的思路是直接强行遍历如果遍历到 nil 就证明这个链表没有环如果一直无限循环超出了题目给了用例长度那就证明没有环你别说之前还过了
当然我现在写这道题就是用标准的快慢指针的写法slow 指针一次走一步fast 指针一次走两步他们如果链表有环那他们迟早会相遇。代码如下
代码
package main
import . nc_tools
/** type ListNode struct{* Val int* Next *ListNode* }*//*** * param head ListNode类 * return bool布尔型
*/
func hasCycle( head *ListNode ) bool {slow : headfast : headfor fast ! nil fast.Next ! nil {slow slow.Nextfast fast.Next.Nextif slow fast {return true}}return false
}
过啦 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
