外贸商城网站系统,大庆市建设局宫方网站,网页排版软件,电子邮箱怎么注册148. 排序链表
给你链表的头结点 head #xff0c;请将其按 升序 排列并返回 排序后的链表 。
示例 1#xff1a;
输入#xff1a;head [4,2,1,3] 输出#xff1a;[1,2,3,4] 示例 2#xff1a;
输入#xff1a;head [-1,5,3,4,0] 输出#xff1a;[-1,0,3,4,5] 示…148. 排序链表
给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。
示例 1
输入head [4,2,1,3] 输出[1,2,3,4] 示例 2
输入head [-1,5,3,4,0] 输出[-1,0,3,4,5] 示例 3
输入head [] 输出[]
提示
链表中节点的数目在范围 [0, 5 * 104] 内 -105 Node.val 105
进阶你可以在 O(n log n) 时间复杂度和常数级空间复杂度下对链表进行排序吗
代码
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/
func sortList(head *ListNode) *ListNode {if head nil || head.Next nil {return head}fast, slow : head, headvar pre *ListNodefor fast ! nil fast.Next ! nil {pre slowfast fast.Next.Nextslow slow.Next}pre.Next nil// 这里是个坑 head 和 slowl : sortList(head)r : sortList(slow)return mergeTwoLists(l, r)
}func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {if list1 nil {return list2}if list2 nil {return list1}if list1.Val list2.Val {list2.Next mergeTwoLists(list1, list2.Next)return list2} else {list1.Next mergeTwoLists(list1.Next, list2)return list1}}
