[Swift]LeetCode23. 合并K个排序链表

[Swift]LeetCode23. 合并K个排序链表 | Merge k Sorted Lists

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

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

64ms

 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 mergeKLists(_ lists: [ListNode?]) -> ListNode? {
14         
15         if lists.count == 0 {
16             return nil
17         }
18         var ar = [Int]()
19         
20         for i in 0..<lists.count {
21             var node = lists[i]
22             
23             while node != nil {
24                 ar.append(node!.val)
25                 node = node!.next
26             }
27         }
28         
29         if ar.count == 0 {
30             return nil
31         }
32         
33         ar = ar.sorted()
34         
35         var head = ListNode(ar[0])
36         var node = head
37         for i in 1..<ar.count {
38             node.next = ListNode(ar[i])
39             node = node.next!
40         }
41         
42         return head
43     }
44 }

76ms

 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 mergeKLists(_ lists: [ListNode?]) -> ListNode? {
14     guard !lists.isEmpty else {
15         return nil
16     }
17 
18     var values = [Int]()
19     for list in lists {
20         var head = list
21         while head != nil {
22             values.append(head!.val)
23             head = head!.next
24         }
25     }
26 
27     values = values.sorted()
28     print(values)
29     let result = ListNode(0)
30     var temp: ListNode? = result
31     for value in values {
32         temp?.next = ListNode(value)
33         temp = temp?.next
34     }
35 
36     return result.next
37 }
38 }

84ms

 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 mergeKLists(_ lists: [ListNode?]) -> ListNode? {
14         guard !lists.isEmpty else { return nil }
15         guard lists.count > 1 else { return lists[0] }
16         let left = mergeKLists(Array(lists[0..<(lists.count / 2)]))
17         let right = mergeKLists(Array(lists[((lists.count / 2))...]))
18         return mergeTwoLists(left, right)
19     }
20     
21     func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
22         let prehead = ListNode(-1)
23         var prev: ListNode? = prehead
24         var l1Node: ListNode? = l1
25         var l2Node: ListNode? = l2
26         while let l1 = l1Node, let l2 = l2Node {
27             if l1.val <= l2.val {
28                 prev?.next = l1
29                 l1Node = l1.next
30             } else {
31                 prev?.next = l2
32                 l2Node = l2.next
33             }
34             prev = prev?.next
35         }
36 
37         prev?.next = l1Node ?? l2Node;
38 
39         return prehead.next
40     }
41 }

116ms

 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 mergeKLists(_ lists: [ListNode?]) -> ListNode? {
14         guard lists.count > 0 else{
15             return nil
16         }
17         var left = 0
18         var right = lists.count - 1
19         var _lists = lists
20         while right > 0 {
21             left = 0
22             while left < right {
23                 _lists[left] = merge2Lists(_lists[left], _lists[right])
24                 left += 1
25                 right -= 1
26             }
27         }
28         return _lists[0]
29     }
30     
31     func merge2Lists(_ l1: ListNode?, _ l2: ListNode?) ->ListNode? {
32         let dummy = ListNode(0)
33         var node = dummy
34     
35         var l1 = l1
36         var l2 = l2
37         
38         while l1 != nil && l2 != nil {
39             if l1!.val < l2!.val {
40                 node.next = l1
41                 l1 = l1!.next
42             } else {
43                 node.next = l2
44                 l2 = l2!.next
45             }
46             
47             node = node.next!
48         }
49         
50         node.next = l1 ?? l2
51         
52         return dummy.next
53     }
54 }

120ms

 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 mergeKLists(_ lists: [ListNode?]) -> ListNode? {
14         if lists.count == 0 {
15             return nil;
16         }
17         var listArray = [ListNode]()
18         for listNode in lists {
19             var listNode = listNode
20             while listNode != nil {
21                 listArray.append(listNode!);
22                 listNode = listNode?.next;
23             }
24         }
25         if listArray.count < 1 {
26             if listArray.count == 0 {
27                 return nil
28             } else {
29                 return listArray[0]     
30             }
31         }
32         listArray.sort { (list1, list2) -> Bool in
33             list1.val < list2.val
34         }
35         for index in 0 ..< (listArray.count - 1) {
36             let node = listArray[index]
37             node.next = listArray[index + 1]
38         }
39         let node = listArray[listArray.count - 1]
40         node.next = nil;
41         return listArray[0]
42     }
43 }

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 mergeKLists(_ lists: [ListNode?]) -> ListNode? {
14         var resultNumbers = [Int]()
15         for linkedList in lists {
16             var currentNode = linkedList
17             while currentNode != nil {
18                 resultNumbers.append(currentNode!.val)
19                 currentNode = currentNode!.next
20             }
21         }
22         resultNumbers = resultNumbers.sorted()
23         
24         var result = ListNode(-1)
25         var currentResultNode = result
26         for num in resultNumbers {
27             currentResultNode.next = ListNode(num)
28             currentResultNode = currentResultNode.next!
29         }
30         
31         return result.next
32     }
33 }

140ms

 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 
13 class Solution {
14     
15     func mergeKLists(_ lists: ArraySlice<ListNode?>) -> ListNode? {
16         let count = lists.endIndex - lists.startIndex
17         guard count > 1 else { return lists.first ??  nil }
18         var nodeOptional1 = lists[lists.startIndex]
19         var nodeOptional2 = lists[lists.startIndex+1]
20         if count > 2 {
21             let midIndex = lists.startIndex + count/2
22             nodeOptional1 = mergeKLists(lists[lists.startIndex..<midIndex])
23             nodeOptional2 = mergeKLists(lists[midIndex..<lists.endIndex])
24         }
25         guard var node1 = nodeOptional1, var node2 = nodeOptional2 else { return nodeOptional1 ?? nodeOptional2 } 
26         let firstVal = min(node1.val, node2.val)
27         var root = ListNode(firstVal)
28         
29         // so that second has a chance
30         let dummieNode = ListNode(0)
31         if node1.val < node2.val {
32             dummieNode.next = node2
33             node2 = dummieNode
34         } else {
35             dummieNode.next = node1
36             node1 = dummieNode
37         }
38         var currentNode = root
39         while let next1 = node1.next, let next2 = node2.next {
40             // print("next vals:", next1.val, next2.val, currentNode!.val)
41             if next1.val < next2.val {
42                 let newNode = ListNode(next1.val)
43                 currentNode.next = newNode
44                 currentNode = newNode
45                 node1 = next1
46             } else {
47                 let newNode = ListNode(next2.val)
48                 currentNode.next = newNode
49                 currentNode = newNode
50                 node2 = next2
51             }
52         }
53         // print("next:", (node1?.next ?? node2?.next)!.val)
54         currentNode.next = node1.next ?? node2.next
55         return root
56     }
57     
58     func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
59         return mergeKLists(lists[lists.startIndex..<lists.endIndex])
60     }
61 }