/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // l1 = [1,2,4]
        // l2 = [1,3,4]

        ListNode* res = new ListNode(0); // dummy
        ListNode* r = res;

        while(l1 || l2)
        {
            while(l1&&(!l2 || l1->val <= l2->val))
            {
                r->next = new ListNode(l1->val);
                r = r->next;
                l1 = l1->next;
                // 만약 next가 더 없으면 종료 혹은 l2 밸류가 더 작으면 종료.
            }
            while(l2&&(!l1 || l2->val <= l1->val))
            {
                r->next = new ListNode(l2->val);
                r = r->next;
                l2 = l2->next;
            }
        }

        return res->next;


    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* L1 = l1;
        ListNode* L2 = l2;
        ListNode* Merged_List = new ListNode;
        ListNode* head = Merged_List;
        while(L1 || L2)
        {
            while(L1 &&(!L2 || L1->val <= L2->val) )
            {
                Merged_List->next = new ListNode(L1->val); // next에 노드를 추가할떄 항상 생성해야한다. 놓치지 말것
                Merged_List = Merged_List->next;
                L1=L1->next;
            }
            while(L2 && (!L1 || L2->val <= L1->val))
            {
                Merged_List->next = new ListNode(L2->val);
                Merged_List = Merged_List->next;
                L2 = L2->next;
            }
        }
        return head->next;

    }
};