Leetcode Easy 21. Merge Two Sorted Lists

2つの単方向LinkedListを小さい順に1つの単方向LinkedListにつなぎ替える。
有名な問題。実際に実装してみると、慣れていないとかなり面倒である。

ポイント
与えられる２つのListは既にSortされている
一つ目から順に比較して、ポインタをつなぎ変える

実装上の注意
ポインタを３つ用意する。
－１つ目のListの要素ポインタ
－２つ目のListの要素ポインタ
－順に追って行くときに使用する要素ポインタ
それぞれ２つのListの要素比較しながら要素が小さい方を選択し、
現在のポインタを移動させていく。
要素のNextがNULLになったらそのListの最後尾なので、
もう一つのListをNextに指定すればよい。

エッジケース
与えられるLinkedListがNULLの場合
片方がNULLの場合はもう一つのListがそのまま答え
＊両方がNULLのケースが存在するが、これはテストケースに存在しない。
実際はNULLでも返しておくのが良い

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //edge case
        if (l1 == NULL && l2 == NULL)return NULL; //no test case
        else if (l1 == NULL)return l2;
        else if (l2 == NULL)return l1;

        ListNode* p1 = l1;
        ListNode* p2 = l2;
        ListNode* start = new ListNode(-1);
        ListNode* C = start;

         while (1) {
            if (p1->val <= p2->val) {
                C->next = p1;
                C = p1;
                p1 = p1->next;
                if (p1 == NULL) {
                    C->next = p2;
                    break;
                }
            }
            else if (p1->val > p2->val) {
                C->next = p2;
                C = p2;
                p2 = p2->next;
                if (p2 == NULL) {
                    C->next = p1;
                    break;
                }
            }
        }
        return start->next;
    }
 };