Problem Statement
Sort a linked list in O(n log n) time using constant space complexity.
Original LeetCode problem page
My Solution in Swift
I used a bottom-up iterative merge-sort to solve this problem with O(n log n) time efficiency and O(1) space efficiency. Note that, you cannot use traditional recursive merge-sort to tackle this problem; otherwise, you will end up use O(log n) stack space for recursive function calls, which is unsatisfying of the question requirement.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
class ListNode { var val: Int var next: ListNode? init(val: Int) { self.val = val } convenience init(val: Int, next: ListNode) { self.init(val: val) self.next = next } } func sortList(var head: ListNode?) -> ListNode? { var size = -1, count = 0 var step = 1 var leftListNode: ListNode? = head var rightListNode: ListNode? = leftListNode var lastMergeNode: ListNode? = nil while size < 0 || step < size { // find rightListHead var i = step while rightListNode != nil && i > 0 { rightListNode = rightListNode!.next --i if size < 0 { --size } } if rightListNode == nil { // reaches the end if size < 0 { size = -size - 1 } step *= 2 leftListNode = head rightListNode = leftListNode lastMergeNode = nil } else { // start merge var i = step, j = step while i > 0 || j > 0 { var node: ListNode if (i > 0 && j > 0 && leftListNode!.val <= rightListNode!.val) || j == 0 { node = leftListNode! if i > 1 { leftListNode = leftListNode!.next } --i } else { node = rightListNode! rightListNode = rightListNode!.next if rightListNode == nil { j = 0 } else { --j } if size < 0 { --size } } if lastMergeNode != nil { lastMergeNode!.next = node } else { head = node } lastMergeNode = node } leftListNode = rightListNode lastMergeNode!.next = rightListNode } } return head } |
Try It Yourself
1: each links to a blog post of mine that is dedicated to the problem
2: total execution time of a solution on my MacBook Pro (Late 2013, 2.6 GHz Intel Core i7, 16 GB 1600 MHz DDR3). Each solution is compiled with following command:
$ swiftc -O -sdk `xcrun --show-sdk-path --sdk macosx` json.swift main.swift -o mySolution
The total execution time is the average of 10 runs.
3: these test cases are semi-automatically :P retrieved from LeetCode Online Judge system and are kept in JSON format
4: each Xcode project includes everything (my Swift solution to a problem, its JSON test cases and a driver code to test the solution on those test cases)
| Problem1 | Time2 | Test Cases3 | My Xcode Project4 |
| Sort List | 32.593ms |