將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回竿痰。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
/**
* 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* h1=l1; // 原有鏈表的動(dòng)態(tài)指針
ListNode* h2=l2;
ListNode* node= new ListNode(0); // 新建輔助節(jié)點(diǎn)赊淑，作為合并鏈表的暫時(shí)的頭節(jié)點(diǎn)国旷，最后需釋放
ListNode* current =node; // 合并鏈表的動(dòng)態(tài)指針
while(h1&&h2){
if(h1->val<=h2->val){
current->next = h1;
h1=h1->next;
current=current->next;
} // 比較兩個(gè)鏈表的節(jié)點(diǎn)的值误趴，誰小薇芝，就接到合并鏈表的后面蓬抄，動(dòng)態(tài)指針后移
else{
current->next = h2;
h2=h2->next;
current=current->next;
}
} // 等長部分的合并
while(h1){
current->next=h1;
h1=h1->next;
current=current->next;
} // 不等長部分的直接遍歷連接到合并鏈表的后面
while(h2){
current->next=h2;
h2=h2->next;
current=current->next;
}
ListNode* ret=node->next; // 暫時(shí)的頭結(jié)點(diǎn)的后面一個(gè)節(jié)點(diǎn)作為合并完成的節(jié)點(diǎn)
delete node; // 釋放
return ret;
}
};
