leetcode Question 54: 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.

Analysis:

The idea is relative simple, add one list into the other. 
Consider the following conditions:
1. The l1 is empty. Then l2 is the result.
2. current element in l1 > current element in l2, insert current element in l2 before current element of l1.
3. current element in l1 < current element in l2, goto the next element in l1 and compare again.
Step 2 and 3 are in the loop, until l2 is empty.

Code (updated 201403):

This version of code is easy to understand, where one node is used to hold the head of the result (for output), another node is used for the tail of the result list (for insertion), every time check (1) the empty case, (2) the value comparison, and insert proper node into the result list, this will solve the problem. See code below:

/**
 * 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* res = new ListNode(0);
        ListNode* current = res;
        while (true){
            if (!l1){
                current->next = l2;
                break;
            }
            if (!l2){
                current->next = l1;
                break;
            }
            if (l1->val < l2->val){
                current->next = l1;
                l1 = l1->next;
            }else{
                current->next = l2;
                l2 = l2->next;
            }
            current = current->next;
        }
        return res->next;
    }
};

Code(updated 201401):

/**
 * 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) {
        if (!l1){return l2;} //if l1 empty, return l2
        if (!l2){return l1;} //if l2 empty, return l1
        ListNode *q=new ListNode(0); //megere l2 into l1
        q->next = l1;
        l1 = q;
        ListNode *p = l2;
        while (p){ //loop to l2 end 
            if (q->next){ // if l1 is not end
                if (p->val<q->next->val){ //if l2 value < l1 vaule, then insert
                    ListNode* tmp;
                    tmp=q->next;
                    q->next = p;
                    p=p->next;
                    q->next->next = tmp;
                }else{q=q->next;} // else goto the next l1 element.
            }else{ // if l1 is end, just link the remaining of l2 to the end and return
                q->next=p;
                return l1->next;
            }
        }
        return l1->next;
    }
};

Code(old version):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merg2(ListNode* l1, ListNode* l2){
        ListNode* head = new ListNode(0);
        head->next = l1;
        ListNode* prev = head;
        if (l1==NULL){
            head->next=l2;
        }
        while (l1!=NULL && l2!=NULL){
            if (l1->val < l2->val){
                if (l1->next != NULL){
                    prev = l1;
                    l1=l1->next;
                }else{
                    l1->next = l2;
                    break;
                }
            }else{
                ListNode* tmp = l2->next;
                prev->next = l2;
                l2->next = l1;
                prev = l2;
                l2 = tmp;
            }
        }
        return head->next;
    }
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return merg2(l1,l2);
    }
};