21. Merge Two Sorted Lists(C++)


LeetCodeの問題ですが、今回は2つの解答例を紹介します。

既存のListNodeを並び替える方法

指定される2つの引数はそれぞれメンバ「next」の値が変更されるためinout引数となりますが、ListNodeの生成時間分は処理が早くなります。

引数はそれぞれ先頭のNodeは変わらず、nextからマージされた結果に変換されます。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy_head = new ListNode();
        ListNode* merged = dummy_head;
        ListNode* current1 = list1;
        ListNode* current2 = list2;
        while (current1 != nullptr && current2 != nullptr) {
            if (current1->val <= current2->val) {
                merged->next = current1;
                current1 = current1->next;
            } else {
                merged->next = current2;
                current2 = current2->next;
            }
            merged = merged->next;
        }
        if (current1 != nullptr) {
            merged->next = current1;
        } else {
            merged->next = current2;
        }
        return dummy_head->next;
    }
};

新たなListNodeを生成する方法

問題では指定されていないので、並び替えるだけでも、新たに生成するでもよいですが、新しくインスタンスを生成する方法も置いておきます。

個人的にinout引数は直観的ではない且つ、欲しい情報があるなら全てreturnで返すべきと思っているので前述のコードはあまり好きではないです。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy_head = new ListNode();
        ListNode* merged = dummy_head;
        ListNode* current1 = list1;
        ListNode* current2 = list2;
        while (current1 != nullptr && current2 != nullptr) {
            if (current1->val <= current2->val) {
                merged->next = new ListNode(current1->val);
                current1 = current1->next;
            } else {
                merged->next = new ListNode(current2->val);
                current2 = current2->next;
            }
            merged = merged->next;
        }
        while (current1 != nullptr) {
            merged->next = new ListNode(current1->val);
            merged = merged->next;
            current1 = current1->next;
        }
        while (current2 != nullptr) {
            merged->next = new ListNode(current2->val);
            merged = merged->next;
            current2 = current2->next;
        }
        return dummy_head->next;
    }
};

ListNode系の問題を解くうえで最初のキーになるのがdummy_headかなと個人的には思っています。
参考になれば幸いです。

以上です!

,

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です