21. 合并两个有序链表

简介: 21. 合并两个有序链表

题目描述

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

示例 1:

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

输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []

输出:[]

示例 3:

输入:l1 = [], l2 = [0]

输出:[0]

解题思路

这个题目很简单,直接依次遍历,小的尾插,为了方便操作,我们引入带头的节点。

代码

迭代版本

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head=new ListNode;
        ListNode* tail=head;
        while(list1||list2)
        {
            if(list1)
            {
                if(list2)
                {
                    if(list1->val<list2->val) tail->next=list1,list1=list1->next;
                    else tail->next=list2,list2=list2->next;
                }
                else
                {
                    tail->next=list1;
                    break;
                }
                
            }
            else
            {
                tail->next=list2;
                break;
            }

            tail=tail->next;
        }
        return head->next;
    }
};

递归版本

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
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;
        }
    }
};
相关文章
|
1月前
|
算法
LeetCode刷题---21.合并两个有序链表(双指针)
LeetCode刷题---21.合并两个有序链表(双指针)
LeetCode | 21. 合并两个有序链表
LeetCode | 21. 合并两个有序链表
|
1天前
21. 合并两个有序链表
21. 合并两个有序链表
|
1月前
|
存储 算法
头歌:第1关:有序单链表的插入操作
头歌:第1关:有序单链表的插入操作
168 0
|
6天前
|
SQL 算法 数据挖掘
LeetCode 二十一:合并两个有序链表 【python】
LeetCode 二十一:合并两个有序链表 【python】
|
10天前
|
算法 安全 Java
【经典算法】LeetCode 21:合并两个有序链表Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 21:合并两个有序链表Java/C/Python3实现含注释说明,Easy)
13 1
|
18天前
题目----力扣--合并两个有序链表
题目----力扣--合并两个有序链表
16 0
|
19天前
|
索引
【力扣刷题】回文链表、环形链表、合并两个有序链表
【力扣刷题】回文链表、环形链表、合并两个有序链表
18 0
|
1月前
【力扣】21. 合并两个有序链表
【力扣】21. 合并两个有序链表
|
1月前
|
C++
有序链表的操作(底层c++实现)
有序链表的操作(底层c++实现)