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. 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) return l2;13         if(l2 == NULL) return l1;14         ListNode * root = new ListNode(-1);15         ListNode * helper = root;16         while(l1!=NULL && l2!=NULL){17             if(l1->val <= l2->val)18                 root->next = l1, l1=l1->next;19             else if(l1->val > l2->val)20                 root->next = l2, l2=l2->next;21             root = root->next;22         }23         while(l1!=NULL){24             root->next = l1;25             l1 = l1->next;26             root = root->next; 27         }28         while(l2!=NULL){29             root->next = l2;30             l2 = l2->next;31             root = root->next; 32         }33         return helper->next;34     }35 };

 

1 public class Solution { 2     public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 3         ListNode helper = new ListNode(0); 4         ListNode ret = helper; 5         if(l1 == null) return l2; 6         if(l2 == null) return l1; 7         while(l1 != null && l2 != null){ 8             if(l1.val < l2.val){ 9                 helper.next = l1;10                 l1 = l1.next;11             }else{12                 helper.next = l2;13                 l2 = l2.next;14             }15             helper = helper.next;16         }17         while(l1 != null){18             helper.next = l1;19             l1 = l1.next;20             helper = helper.next;21         }22         while(l2 != null){23             helper.next = l2;24             l2 = l2.next;25             helper = helper.next;26         }27         return ret.next;28     }29 }