LoginSignup
7

More than 5 years have passed since last update.

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

Last updated at Posted at 2017-08-01

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
7