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.

思路：1. 一般做法。用两个指针分别指两条链表，一个一个比较。

        2.用一个指针，将整个链表按大小串起来。

注意“等号”用在何时！！！容易错.

/**
 * 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==NULL) return l2;
        else if(l2==NULL) return l1;
    
        ListNode *p1=l1;
        ListNode *p2=l2;
        ListNode *head,*t;
        
        if(l1->val<=l2->val) head=l1;
        else head=l2;
        
        while(p1 && p2 ){
            if(p1->val<=p2->val){
                if(p1->next && p1->next->val<=p2->val) p1=p1->next;
                else {
                    t=p1;
                    p1=p1->next;
                    t->next=p2;
                }
            }else{
                if(p2->next && p2->next->val<p1->val) p2=p2->next;
                else{
                    t=p2;
                    p2=p2->next;
                    t->next=p1;
                }
            }
        }
        return head;
    }
};

2.代码更简洁！！！

/**
 * 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==NULL) return l2;
        if(l2==NULL) return l1;
    
        ListNode *head,*t;
        if(l1->val<=l2->val) {head=l1;l1=l1->next;}
        else {head=l2;l2=l2->next;}
        t=head;
        
        while(l1 && l2){
            if(l1->val<=l2->val) {t->next=l1;l1=l1->next;}
            else {t->next=l2;l2=l2->next;}
            t=t->next;
        }
        
        if(l1) t->next=l1;
        else t->next=l2;
        
        return head;
    }
};