LeetCodeの問題ですが、今回は2つの解答例を紹介します。
既存のListNodeを並び替える方法
指定される２つの引数はそれぞれメンバ「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かなと個人的には思っています。
参考になれば幸いです。
以上です！