問題:Merge Two Sorted ListNodes (二つの連結リストを繋げる)
タイトルの通りですが、二つの連結リストを昇順に繋げてください。
- 連結リストの中のData(この場合Int)は順番に入ってることにしましょう。
- ListNodeのリンクはどこまで続いているかわからないです。
連結リストってなに!?という人がいれば、こちらを読んでください。
ListNodeのクラスはこちらを使ってください。
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}
メソッド:
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
//ここにコードを書く
}
実行例:
// List1
var node0 = ListNode(11)
var node1 = ListNode(10)
node1.next = node0
var node2 = ListNode(4)
node2.next = node1
var node3 = ListNode(1)
node3.next = node2
// List2
var nodeA = ListNode(9)
var nodeB = ListNode(3)
nodeB.next = nodeA
var nodeC = ListNode(2)
nodeC.next = nodeB
//実行メソッド:それぞれの頭のListNodeを渡しています。
var merged = mergeTwoLists(node3, nodeC)
//merged が繋がったNodeListです。それぞれHeadからTailまでの値をプリントしています。
while merged?.val != nil{
print(merged?.val ?? 0)
merged = merged?.next
}
実行結果
1
2
3
4
9
10
11
Program ended with exit code: 0
ヒント:
それぞれのListNodeの値の大きさを比較して、それによりどっちのListNodeをリンクさせるか判定させる。
解答:
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
let dummy = ListNode(0)
var node = dummy
var l1 = l1
var l2 = l2
while l1 != nil && l2 != nil{
if l1!.val < l2!.val {
node.next = l1
l1 = l1!.next
} else{
node.next = l2
l2 = l2!.next
}
node = node.next!
}
node.next = l1 ?? l2
return dummy.next
}
メモ / ポイント
自分の回答ではなく、この方の回答を見ました。
https://github.com/soapyigu/LeetCode_Swift/blob/master/LinkedList/MergeTwoSortedLists.swift