LeetCode in Swift: Sort List

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.

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)

Problem1Time2Test Cases3My Xcode Project4
Sort List32.593ms Save  (412) Save  (455)

More Problems Solved in Swift

My full list of LeetCode problems attempted using Swift