###### tags: `LeetCode` `Easy` `Two Pointer` `Linked List` `Merge Sort`
# LeetCode #21 [Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)
### (Easy)

將兩個升序鏈結串列合併為一個新的 升序 鏈結串列並返回。新鏈結串列是通過拼接給定的兩個鏈結串列的所有節點組成的。


---
當l1與l2皆存在時, 比較兩節點的值, 選取較小的值並以此創建一個新的鏈結節點並加入鏈結串列中, 然後將其值被加入的鏈結串列往後探索一個節點, 直到l1或l2其中一個為空指標, 此時將另一個鏈結串列的節點遍歷, 並依序新增鏈結節點並加入到回傳鏈結串列中。

---

/**
 * 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 *tmp = nullptr, *ans = nullptr, *prev = nullptr;
        while(l1&&l2){
            if(l1->val<=l2->val){
                ListNode *tmp = new ListNode(l1->val);
                if(!prev)ans = tmp;
                else prev->next = tmp;
                prev = tmp;
                l1 = l1->next;
            }
            else{
                ListNode *tmp = new ListNode(l2->val);
                if(!prev)ans = tmp;
                else prev->next = tmp;
                prev = tmp;
                l2 = l2->next;
            }
        }
        if(l1){
            while(l1){
                ListNode *tmp = new ListNode(l1->val);
                if(!prev)ans = tmp;
                else prev->next = tmp;
                prev = tmp;
                l1 = l1->next;
            }
        }
        else if(l2){
            while(l2){
                ListNode *tmp = new ListNode(l2->val);
                if(!prev)ans = tmp;
                else prev->next = tmp;
                prev = tmp;
                l2 = l2->next;
            }
        }
        return ans;
    }
};