21. 合并两个有序链表

1.题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

2.示例

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
1
2

输入：l1 = [], l2 = [0]
输出：[0]
1
2

3.答案

①迭代

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {  
        if(!list1) return list2;  //list1为空，直接返回
        if(!list2) return list1; //list2为空，直接返回
       // 新增虚拟头节点
        ListNode *l=new ListNode(-1),*pre=l;
        while(list1&&list2){  //不断插入 list1和list2中值较小的结点
            if(list1->val<=list2->val){
              pre->next=list1;
              list1=list1->next;
            }else{
                pre->next=list2;
                list2=list2->next;
            }
            pre=pre->next;  //pre一直向下移动，才可以一直在后面插入新元素
        }
    if(list1) pre->next=list1;  //list1还有元素未插入
    if(list2) pre->next=list2;  //list2还有元素未插入
        l=l->next;
        return l;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

②递归

终止条件：只要有一个链表为空就可以返回另一个链表
返回值：每次排序好的链表头结点
递归内容: 如果 list1 的 val 值更小，则将 list1.next 与list2 合并排序，排序好的链表头作为新的list1.next，l2 同理

 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {  
        if(!list1) return list2;  //list1为空，直接返回
        if(!list2) return list1; //list2为空，直接返回
   		if(list1->val<=list2->val) {  // list1的val更小，由list1作为头结点
   		list1->next=mergeTwoLists(list1->next,list2);  //对之后结点进行合并排序,并返回其链表头作为next
   		return list1;
   		}else{ // list2的val更小，由list2作为头结点
   		list2->next=mergeTwoLists(list1,list2->next);//对之后结点进行合并排序，并返回其链表头作为next
   		return list2;
   		}
    }
1
2
3
4
5
6
7
8
9
10
11