前言
持续更新了
正文
问题来源
本问题来自leetcode上的148题。
问题描述
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
分析：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func sortList(head *ListNode) *ListNode {
//var fast, slow, prev *ListNode
if head == nil || head.Next == nil {
return head
}
fast, slow, prev := head, head, head
for fast != nil && fast.Next != nil {
prev = slow
slow = slow.Next
fast = fast.Next.Next
}
prev.Next = nil // split to 2 parts
return merge2SortList(sortList(head), sortList(slow))
}
func merge2SortList(h1 *ListNode, h2 *ListNode) *ListNode {
if h1 == nil {
return h2
}
if h2 == nil {
return h1
}
if h1.Val > h2.Val {
h2.Next = merge2SortList(h1, h2.Next)
return h2
}
h1.Next = merge2SortList(h1.Next, h2)
return h1
}
总结：
勤思考。
结语
不管怎么样好好加油。
