説明#
2 つのソートされたリストをマージして、新しいソートされたリストを作成して返します。新しいリストは、与えられた 2 つのリストのすべてのノードを連結して作成されます。
例：
入力：1->2->4, 1->3->4
出力：1->1->2->3->4->4
アプローチ#
- どちらかのリストが空の場合、もう一方のリストを返します。どちらのリストも空でない場合でも、このルールに従います。
- より小さい最初の要素を持つリストを挿入されるリストとし、もう一方を挿入するリストとします。挿入されるリストが最終的に返されるリストです。
- 挿入されるリストが空でないか、挿入するリストに次の要素がある場合、挿入するリストの要素が挿入するリストの次の要素以下である場合、その要素を次の要素の前に挿入します。そうでない場合、現在の挿入するリストを進めます。
- 挿入するリストにまだ要素がある場合（前のプロセスでは挿入されません）、それを挿入するリストの後に直接接続する必要があります。
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
struct ListNode* l_get_buffer,*l_set_buffer,*l_final,*l_get,*l_set;
//どちらかのリストが空の場合
if(!(l1 && l2)) {
return l1?l1:l2;//l1が空でない場合はl1を返し、そうでない場合はl2を返します
}
//l_setをより小さい最初の要素に設定します
l_set = (l1->val <= l2->val)?l1:l2;
l_get = (l_set == l1)?l2:l1;
//最終的に返されるリストをより小さい最初のリストに設定します
l_final = l_set;
while (l_get != 0 && l_set->next != 0)
{
if((l_get->val) <= (l_set->next->val)) {
//現在の2つのポインタを記録します
l_get_buffer = l_get;
l_set_buffer = l_set;
//nextポインタを更新します
l_get = l_get->next;
//ポインタを再構成します
l_get_buffer->next = l_set_buffer->next;
l_set_buffer->next = l_get_buffer;
}
else
l_set = l_set->next;
}
//挿入されていない要素がある場合
if(l_get != 0)
l_set->next = l_get;
return l_final;
}
注意#
- 要素を挿入する際に、挿入されるリストのポインタを進めてはいけません。そうすると、挿入されるリストの要素の比較が 1 つスキップされます。