Problem: 21. 合并两个有序链表
文章目录
- 思路
- 1 递归实现
- 2 迭代实现
- Code
思路
方法1 递归实现
方法2 迭代实现
1 递归实现
分析问题
对于本题，合并两个有序链表A和B，mergeTwoLists（A,B），递归只需要关注本层我要干什么？，返回什么？首先我要先直到A，B 哪个链表的头最小，让最小的那个节点指向剩余部分合并的有序链表头，然后返回当前的结点头。
基本情况
- 当A为空的时候，直接返回B，因为这意味着B所有的结点都大于A的所有结点。
- 当B为空的时候，直接返回A，同理。
class Solution {
public:
// 递归实现
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1 == nullptr ) return list2 ;
if(list2 == nullptr ) return list1 ;
if(list1->val < list2->val) {
list1->next = mergeTwoLists(list1->next,list2) ;
return list1 ;
}else {
list2->next = mergeTwoLists(list1 , list2->next) ;
return list2 ;
}
}
};2 迭代实现
创建一个新的节点preHead ，遍历两个链表，每次让新节点指向两个链表中的最小的一个结点，更新
preHead。
Code
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 创建一个新节点
ListNode* preHead = new ListNode(-1);
ListNode* prev = preHead;
while(l1 && l2 ) {
if(l1->val <= l2->val ) {
prev->next = l1 ;
l1 = l1->next ;
}else {
prev->next = l2 ;
l2 = l2->next ;
}
prev = prev->next ;
}
if(l1 == nullptr ) {
prev->next = l2 ;
}else {
prev->next = l1 ;
}
preHead = preHead->next ;
return preHead ;
}
};