[Swift]LeetCode148. 排序链表 | Sort List
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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
Example 2:
Input: -1->5->3->4->0 Output: -1->0->3->4->5
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3 输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0 输出: -1->0->3->4->5
124ms
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * public var val: Int
5 * public var next: ListNode?
6 * public init(_ val: Int) {
7 * self.val = val
8 * self.next = nil
9 * }
10 * }
11 */
12 class Solution {
13 func sortList(_ head: ListNode?) -> ListNode? {
14 var arr = [Int]()
15 var cur = head
16
17 while cur != nil {
18 arr.append(cur!.val)
19 cur = cur!.next
20 }
21
22 arr.sort()
23
24 if arr.count < 2 {
25 return head
26 } else {
27
28 var head = ListNode(arr[0])
29 var curr: ListNode? = head
30
31 for i in 1..<arr.count {
32 curr?.next = ListNode(arr[i])
33 curr = curr?.next
34 }
35
36 return head
37 }
38 }
39 }128ms
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * public var val: Int
5 * public var next: ListNode?
6 * public init(_ val: Int) {
7 * self.val = val
8 * self.next = nil
9 * }
10 * }
11 */
12 class Solution {
13 func sortList(_ head: ListNode?) -> ListNode? {
14 var nums = [Int]()
15 var node = head
16
17 while node != nil {
18 nums.append(node!.val)
19 node = node!.next
20 }
21
22 nums.sort()
23
24 var mockNode = ListNode(0)
25 node = mockNode
26
27 for num in nums {
28 node?.next = ListNode(num)
29 node = node?.next
30 }
31
32 return mockNode.next
33
34 }
35 }220ms
1 extension ListNode {
2 func length() -> Int {
3 return 1 + (self.next?.length() ?? 0)
4 }
5 }
6
7 class Solution {
8 func sortList(_ head: ListNode?) -> ListNode? {
9 guard let head = head else {
10 return nil
11 }
12 return divideAndMerge(head, length: head.length())
13 }
14
15 func divideAndMerge(_ head: ListNode?, length: Int) -> ListNode? {
16 guard length > 1 else {
17 return head
18 }
19
20 let mid: ListNode? = {
21 var current = head
22 var previous = head
23 for _ in 0..<length / 2 {
24 previous = current
25 current = current?.next
26 }
27 previous?.next = nil
28 return current
29 }()
30
31 let left = divideAndMerge(head, length: length / 2)
32 let right = divideAndMerge(mid, length: length - (length / 2))
33 return merge(left, mid: right)
34 }
35
36 func merge(_ head: ListNode?, mid: ListNode?) -> ListNode? {
37 var head = head
38 var mid = mid
39 var mergedList: ListNode?
40 var endNode: ListNode?
41
42 while let headNode = head, let midNode = mid {
43 var currentNode: ListNode!
44 if headNode.val < midNode.val {
45 currentNode = headNode
46 head = headNode.next
47 headNode.next = nil
48 } else {
49 currentNode = midNode
50 mid = midNode.next
51 midNode.next = nil
52 }
53 if mergedList == nil {
54 endNode = currentNode
55 mergedList = currentNode
56 } else {
57 endNode?.next = currentNode
58 endNode = currentNode
59 }
60 }
61 if let headNode = head {
62 endNode?.next = headNode
63 } else {
64 endNode?.next = mid
65 }
66 return mergedList
67 }
68 }268ms
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * public var val: Int
5 * public var next: ListNode?
6 * public init(_ val: Int) {
7 * self.val = val
8 * self.next = nil
9 * }
10 * }
11 */
12 class Solution {
13 func sortList(_ head: ListNode?) -> ListNode? {
14 if head == nil || head?.next == nil {
15 return head
16 }
17
18 // split in half
19 var slow = head, fast = head?.next
20 while fast != nil && fast?.next != nil {
21 slow = slow?.next
22 fast = fast?.next?.next
23 }
24
25 // break the list
26 let secondHead = slow?.next
27 slow?.next = nil
28 var l1 = self.sortList(secondHead)
29 var l2 = self.sortList(head)
30
31 var resHead: ListNode? = nil
32 var resTail: ListNode? = nil
33 var next: ListNode? = nil
34 while let l1a = l1, let l2a = l2 {
35 if l1a.val < l2a.val {
36 next = l1
37 l1 = l1a.next
38 } else {
39 next = l2
40 l2 = l2a.next
41 }
42
43 resHead = resHead ?? next
44 resTail?.next = next
45 resTail = next
46
47 }
48
49 if l1 != nil {
50 resTail?.next = l1
51 } else if l2 != nil {
52 resTail?.next = l2
53 }
54
55 return resHead
56 }
57 }296ms
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * public var val: Int
5 * public var next: ListNode?
6 * public init(_ val: Int) {
7 * self.val = val
8 * self.next = nil
9 * }
10 * }
11 */
12 class Solution {
13 func sortList(_ head: ListNode?) -> ListNode? {
14 guard let head = head else{
15 return nil
16 }
17 guard head.next != nil else{
18 return head
19 }
20 var cur:ListNode? = head
21 var length = 0
22 while cur != nil{
23 length += 1
24 cur = cur!.next
25 }
26 let dummy = ListNode(-1)
27 dummy.next = head
28 var left:ListNode? ,right:ListNode?,tail:ListNode?
29 var step = 1
30 while step < length{
31 cur = dummy.next
32 tail = dummy
33 while(cur != nil){
34 left = cur
35 right = split(left,step)
36 cur = split(right,step)
37 tail = merge(left,right,tail)
38 }
39
40 step = step << 1
41 }
42 return dummy.next
43
44 }
45 func split(_ head:ListNode? ,_ n:Int) -> ListNode?{
46 guard let head = head else{
47 return nil
48 }
49 var phead:ListNode? = head
50 for _ in 1..<n{
51 if phead != nil{
52 phead = phead!.next
53 }
54 }
55 if phead == nil{
56 return nil
57 }
58 let secondNode = phead!.next
59 phead!.next = nil
60 return secondNode
61 }
62 func merge(_ l1:ListNode?, _ l2:ListNode?, _ head:ListNode?) -> ListNode?{
63 var cur:ListNode? = head
64 var l1 = l1,l2 = l2
65 while l1 != nil && l2 != nil{
66 if l1!.val > l2!.val{
67 cur!.next = l2
68 cur = l2
69 l2 = l2!.next
70 }else{
71 cur!.next = l1
72 cur = l1
73 l1 = l1!.next
74 }
75 }
76 cur!.next = l1 == nil ? l2 : l1
77 while(cur!.next != nil) {
78 cur = cur!.next
79 }
80 return cur
81 }
82 }336ms
1 /**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 * public var val: Int
5 * public var next: ListNode?
6 * public init(_ val: Int) {
7 * self.val = val
8 * self.next = nil
9 * }
10 * }
11 */
12 class Solution {
13 func sortList(_ head: ListNode?) -> ListNode? {
14 if head == nil || head?.next == nil { return head }
15
16 let middle = findMiddle(head)
17 let l2 = sortList(middle?.next)
18 middle?.next = nil
19 let l1 = sortList(head)
20 return merge(l1, l2)
21 }
22
23
24 private func merge(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
25 var dummy = ListNode(0), tail = dummy
26 var l1 = l1, l2 = l2
27
28 while l1 != nil && l2 != nil {
29 if l1!.val < l2!.val {
30 tail.next = l1
31 l1 = l1?.next
32 }else {
33 tail.next = l2
34 l2 = l2?.next
35 }
36 tail = tail.next!
37 }
38 if l1 != nil {
39 tail.next = l1
40 }else if l2 != nil {
41 tail.next = l2
42 }
43
44 return dummy.next
45 }
46
47
48 private func findMiddle(_ head: ListNode?) -> ListNode? {
49 var slow = head, fast = head
50 while fast?.next != nil && fast?.next?.next != nil {
51 slow = slow?.next
52 fast = fast?.next?.next
53 }
54 return slow
55 }
56 }