/**
* 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(100); // 定义一个头结点
ListNode* p = HEAD;
while(l1 && l2){
if(l1->val < l2->val){
p->next = l1;
l1 = l1->next;
p = p->next;
}else{
p->next = l2;
l2 = l2->next;
p = p->next;
}
}
// 此时l1 或者 l2 至少有一个链表已走完了，把另外链表剩下的元素直接连上就可以了
// 直接连上，因为剩下的结点是递增的，不需要一个一个next了
if(l1){
p->next = l1;
}
if(l2){
p->next = l2;
}
return HEAD->next;
}
};
