[swift] LeetCode 148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

1 2	Input: 4->2->1->3 Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

1 2	Input: -1->5->3->4->0 Output: -1->0->3->4->5

func sortList(_ head: ListNode?) -> ListNode? {
    var arr = Array(repeating: 0, count: 256*128)
    var i = 0, p = head
    while let q = p {
        arr[i] = q.val
        p = q.next; i += 1
    }
    arr = Array(arr[..<i]).sorted()

    p = head; i = 0
    while let q = p {
        q.val = arr[i]
        p = q.next; i += 1
    }

    return head
}

func sortList(_ head: ListNode?) -> ListNode? {

var arr = Array(repeating: 0, count: 256*128)

var i = 0, p = head

while let q = p {

arr[i] = q.val

p = q.next; i += 1

}

arr = Array(arr[..<i]).sorted()

p = head; i = 0

while let q = p {

q.val = arr[i]

p = q.next; i += 1

}

return head

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版