跳转至

LC148 - 排序链表

SortList.go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
package LinkedList

// 时间复杂度: O(n * log n), 空间复杂度: O(log n)
func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    fast = slow.Next
    slow.Next = nil
    head1 := sortList(head)
    head2 := sortList(fast)
    newHead := mergeTwoLists(head1, head2)
    return newHead
}

mergeTwoLists函数在LC21中实现。

归并排序，空间复杂度为递归深度O(log n)。