题目
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.
Example:
Input：1->2->4, 1->3->4
Output：1->1->2->3->4->4
思路
思路一：建立一个新链表
建立一个新的链表，用来保存合并的结果。为了方便链表的插入，定义一个临时节点，否则每次都要遍历到节点的尾部进行插入。
思路二：递归法
- 递归的终止条件：
其中一个链表为空 - 递归
- 如果l1->val <= l2->val，则将l1的下一个节点记为l1->next与l2的合并链表
- 如果l1->val > l2->val，则将l2的下一个节点记为l2->next与l1的合并链表
图1：两个链表
图2：第一次递归
图3：第二次递归
C++
- 思路一
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr)
return l2;
if(l2 == nullptr)
return l1;
ListNode* result = new ListNode(0) ;
ListNode* temp = result;
while(l1 != nullptr && l2 != nullptr){
if(l1->val <= l2->val){
temp ->next = l1;
l1 = l1 -> next;
}
else{
temp -> next =l2;
l2 = l2 ->next;
}
temp = temp ->next;
}
if(l1 == nullptr)
temp -> next = l2;
else
temp -> next =l1;
return result -> next;
}
- 思路二
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr)
return l2;
if(l2 == nullptr)
return l1;
if(l1->val <= l2->val){
l1->next = mergeTwoLists(l1->next ,l2);
return l1;
}
else{
l2->next = mergeTwoLists(l2->next ,l1);
return l2;
}
}