-
Notifications
You must be signed in to change notification settings - Fork 0
/
23_merge_k_sorted_lists.swift
91 lines (87 loc) · 3.1 KB
/
23_merge_k_sorted_lists.swift
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
guard let l1 = l1 else { return l2 }
guard let l2 = l2 else { return l1 }
if l1.val < l2.val {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l1, l2.next)
return l2
}
}
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
// Solution 2: Merge by head
guard !lists.isEmpty else { return nil }
var mergedList = lists[0]
for i in 1..<lists.count {
mergedList = mergeTwoLists(mergedList, lists[i])
}
return mergedList
// Solution 1: Brute Force (It works, but it is not efficient enough.)
// guard !lists.isEmpty else { return nil }
// var dummyHead : ListNode? = ListNode(-10001)
// var n : ListNode? = lists[0]
// dummyHead!.next = n
// loop_lists: for i in 1..<lists.count {
// if n == nil {
// n = lists[i]
// dummyHead!.next = n
// continue loop_lists
// }
// var node = lists[i]
// loop_node: while node != nil {
// n = dummyHead!.next // restart
// printLists(n)
// if node!.val < n!.val {
// let temp = node!.next
// dummyHead!.next = node
// node!.next = n!
// node = temp
// continue loop_node
// }
// loop_ans: while n != nil {
// // if smaller than the current node, insert.
// if let next = n!.next {
// if n!.val <= node!.val && node!.val <= next.val {
// let temp = n!.next
// let out_temp = node!.next
// n!.next = node
// node!.next = temp
// node = out_temp
// continue loop_node
// }
// } else if node!.val > n!.val {
// n!.next = node
// break loop_ans
// }
// n = n!.next
// }
// node = node!.next
// }
// }
// return dummyHead!.next
}
// func printLists (_ head: ListNode?) {
// guard var h = head else { return }
// while h != nil {
// print(h.val)
// if let next = h.next {
// h = next
// } else {
// print("===")
// break
// }
// }
// }
}