网站建设费用先付一半,做网站备案好还是不备案好,游戏推广文案,追波设计网站目录
题目#xff1a;链表相加(二)_牛客题霸_牛客网 (nowcoder.com)
题目的接口#xff1a;
解题思路#xff1a;
代码#xff1a;
过啦#xff01;#xff01;#xff01;
题目#xff1a;单链表的排序_牛客题霸_牛客网 (nowcoder.com)
题目的接口#xff1a;…目录
题目链表相加(二)_牛客题霸_牛客网 (nowcoder.com)
题目的接口
解题思路
代码
过啦
题目单链表的排序_牛客题霸_牛客网 (nowcoder.com)
题目的接口
解题思路
代码
过啦
写在最后 题目链表相加(二)_牛客题霸_牛客网 (nowcoder.com) 题目的接口
package main
import . nc_tools
/** type ListNode struct{* Val int* Next *ListNode* }*//*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head1 ListNode类 * param head2 ListNode类 * return ListNode类
*/
func addInList( head1 *ListNode , head2 *ListNode ) *ListNode {// write code here
}
解题思路
这道题我一开始想了不少方法在想怎么用 O(N) 的算法做但是死来想去大多方法都比较麻烦最后就选择了一个代码比较好编写的方法
思路如下先把两个链表反转这样就能进行相加的逻辑了然后再依次相加即可虽然遍历了三遍但还是一个 O(N) 的算法
代码
package main
import . nc_tools
/** type ListNode struct{* Val int* Next *ListNode* }*//*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head1 ListNode类 * param head2 ListNode类 * return ListNode类
*/
func addInList( head1 *ListNode , head2 *ListNode ) *ListNode {head1 reverse(head1)head2 reverse(head2)var res *ListNodevar carry intfor head1 ! nil || head2 ! nil || carry 0 {var sum intif head1 ! nil {sum head1.Valhead1 head1.Next}if head2 ! nil {sum head2.Valhead2 head2.Next}res ListNode{Val: (sum carry)%10,Next: res,}carry (sum carry)/10}return res
}func reverse(head *ListNode) *ListNode {var next *ListNodevar prev *ListNodefor head ! nil {next head.Nexthead.Next prevprev headhead next}return prev
}
过啦 题目单链表的排序_牛客题霸_牛客网 (nowcoder.com) 题目的接口
package main
import . nc_tools
/** type ListNode struct{* Val int* Next *ListNode* }*//*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head ListNode类 the head node* return ListNode类
*/
func sortInList( head *ListNode ) *ListNode {// write code here
}
解题思路
怎么说呢这道题我是直接链表转数组再数组排序转回链表实际上是有两种其他的方法的一个是用归并排序来做但是我实际上不太会归并啦
另一种就是不调库自己实现一份快排或者其他 nlogn 的排序这个面试的时候看面试官怎么想吧反正我现在是偷懒调库了~
代码
package mainimport . nc_tools
import sort/** type ListNode struct{* Val int* Next *ListNode* }*//*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param head ListNode类 the head node* return ListNode类*/
func sortInList( head *ListNode ) *ListNode {cur : headnum : []int{}for cur ! nil {num append(num, cur.Val)cur cur.Next}sort.Ints(num)cur headi : 0for cur ! nil {cur.Val num[i]cur cur.Nexti}return head
}过啦 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
