Day 12, 21 Merge Two Sorted Lists

Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
 ---------------------------------
Solution #1
handle 2 special cases at the beginning,
1) either l1 or l2 is NULL, or both are NULL
2) either l1 or l2 has only one element, or both have only one element

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (l1 == NULL) {
            return l2;
        }
        if (l2 == NULL) {
            return l1;
        }
        
        ListNode *saved, *pre;
        if (l1->val < l2->val) {
            saved = l1;
            pre = l1;
            l1 = l1->next;
            pre->next = l2;
        }else {
            saved = l2;
            pre = l2;
            l2 = l2->next;
            pre->next = l1;
        }
        
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                pre->next = l1;
                pre = l1;
                l1 = l1->next;
                pre->next = l2;
            }else {
                pre->next = l2;
                pre = l2;
                l2 = l2->next;
                pre->next = l1;
            }
        }
        return saved;
    }
};

Solution #2
recursion

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (l1 == NULL) {
            return l2;
        }
        if (l2 == NULL) {
            return l1;
        }
        ListNode *re;
        if (l1->val < l2->val) {
            re = l1;
            re->next = mergeTwoLists(l1->next,l2);
        }else {
            re = l2;
            re->next = mergeTwoLists(l1,l2->next);
        }
        return re;
    }
};

Solution #3, from others
cur saves the address of the "next" in last node

class Solution {  
public:  
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {  
        ListNode* ret = NULL;  
        ListNode** cur = &ret;  
        while(NULL != l1 && NULL != l2)  
        {  
            if(l1->val < l2->val)  
            {  
                *cur = l1;  
                cur = &(l1->next);  
                l1 = l1->next;  
            }  
            else  
            {  
                *cur = l2;  
                cur = &(l2->next);  
                l2 = l2->next;  
            }  
        }  
        *cur = NULL == l1? l2: l1;  
        return ret;  
    }  
};  

update
Solution #4, using dummy head

/**
 * 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) {
        ListNode* dummy = new ListNode(0);
        ListNode* itr = dummy;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                itr->next = l1;
                itr = l1;
                l1 = l1->next;
            }else {
                itr->next = l2;
                itr = l2;
                l2 = l2->next;
            }
        }
        if (l1 == NULL) {
            itr->next = l2;
        }else {
            itr->next = l1;
        }
        return dummy->next;
    }
};