[Swift]LeetCode148.排序链表|SortList

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 }