/**
* 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;
};