アルゴリズム
algorithm
Swift

面接で絶対に押さえておきたいアルゴリズム問題(7) ~ ListNode(連結リスト)~

More than 1 year has passed since last update.


問題: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