21. 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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4


合并两个有序单链表


C++（13ms）：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
12         if (l1 == NULL)
13             return l2 ;
14         if (l2 == NULL)
15             return l1 ;
16         ListNode* head = NULL ;
17         if (l1->val <= l2->val){
18             head = l1 ;
19             l1 = l1->next ;
20         }else{
21             head = l2 ;
22             l2 = l2->next ;
23         }
24         ListNode* p = head ;
25         while(l1 != NULL && l2 != NULL){
26             if (l1->val <= l2->val){
27                 p->next = l1 ;
28                 l1 = l1->next ;
29             }else{
30                 p->next = l2 ;
31                 l2 = l2->next ;
32             }
33             p = p->next ;
34         }
35         p->next = l1 ? l1 : l2 ;
36         return head ;
37     }
38 };