Leetcode --- Merge Two Sorted Lists
===

## Iteration

類似使用兩個pt去指向當前要比較的對象，依序往下比較

/**
 * 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* list1, ListNode* list2) {
        ListNode* resHead= new ListNode();
        auto resPt= resHead;
        while(list1 || list2)
        {
            
            if(list1 == NULL)
            {
                resPt->next= list2;
                break;
            }
            else if(list2 == NULL)
            {
                resPt->next= list1;
                break;
            }
            else
            {
                auto cur= new ListNode();
                if(list1->val <= list2->val)
                {
                    cur->val= list1->val;
                    list1= list1->next;
                }
                else
                {
                    cur->val= list2->val;
                    list2= list2->next;
                }
                resPt->next= cur;
                resPt= resPt->next;
            }
        }
        auto tmp= resHead;
        resHead= resHead->next;
        delete tmp;
        return resHead;
    }
};

## Recursion

核心想法: mergeTwoLists這個function會幫我處理除了當前節點外的排序

case 1: l1或l2為空，返回l2或l1
case 2: l1.val <= l2，確定l1是比較小的，所以l1.next去接排序好的list(就是mergeTwoLists)
case 3: l1.val > l2，跟case2相反

/**
 * 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* list1, ListNode* list2) {
        if(!list1) return list2;
        if(!list2) return list1;

        if(list1->val <= list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next= mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};