/**
* 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= NULL;//头指针
ListNode*cur= NULL;//当前操作的点
ListNode*p =l1;
ListNode*q =l2;
while(p&&q)
{if (head == NULL)
{if (p->val<q->val)
{
head = cur= p;
p= p->next;
head->next = NULL;
}
else
{
head = cur = q;
q= q->next;
head->next = NULL;
}
}
else
{
if (p->val<q->val)
cur->next= p;
cur= cur->next ;
cur->next = NULL;
}
else
{
cur->next= q;
cur= cur->next ;
q= q->next;
cur->next = NULL;
}
}
if(p!= NULL)
cur->next= p;
else if(q!= NULL)
cur->next = q;
return head;
};