2019-01-30 Day25

1.合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

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