【面试必刷TOP101】链表相加单链表的排序

题目：链表相加(二)_牛客题霸_牛客网 (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
}