Problem Statement
Sort a linked list using insertion sort.
Original LeetCode problem page
My Solution in Swift
Every time after inserting a list node, I use a variable to record the reference to that node. When next uninserted list node comes in, it checks from the recorded last inserted node instead of restarting the checking from the head list node. Only if the new list node is smaller than the previous list node of the last inserted list node, the inserting process needs to restart from the very beginning. In this way, the insertion sort algorithm is O(n) in best case and O(n2) in both average and worst case. The space complexity is O(1).
|
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 |
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 insertionSortList(var head: ListNode?) -> ListNode? { if head == nil { return head } var currRemainingNode = head!.next var nextRemainingNode = currRemainingNode?.next head!.next = nil var prevNode: ListNode? = nil var currNode = head while currRemainingNode != nil { while (true) { if currRemainingNode!.val >= currNode!.val { prevNode = currNode currNode = currNode!.next if currNode == nil { prevNode!.next = currRemainingNode currRemainingNode!.next = nil currNode = currRemainingNode break; } } else if prevNode != nil && currRemainingNode!.val < prevNode!.val { // restart search from beginning prevNode = nil currNode = head } else { currRemainingNode!.next = currNode currNode = currRemainingNode if prevNode != nil { prevNode!.next = currRemainingNode } else { head = currRemainingNode } break; } } currRemainingNode = nextRemainingNode nextRemainingNode = nextRemainingNode?.next } 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 |
| Insertion Sort List | 26.869ms |