题目
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的合并链表
![](https://img.zhankr.net/jahmvxm3trj224804.jpg)
图1:两个链表
![](https://img.zhankr.net/ecza2wwydvw224805.jpg)
图2:第一次递归
![](https://img.zhankr.net/4kqrbqn4jfl224806.jpg)
图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;
}
}