LeetCode刷题---21.合并两个有序链表(双指针)

简介: LeetCode刷题---21.合并两个有序链表(双指针)



一、编程题:21.合并两个有序链表(双指针)

1.题目描述

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

2.示例1:

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

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

3.示例2:

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

输出:[]

4.示例3:

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

输出:[0]

5.提示:

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

二、解题思路

  这题采用双指针,本题主要关键点为:

  • 1.该怎么去移动这两个指针?这一点要理清楚。这里双指针移动就比较简单了,分别向下移动一步即可;
  • 2.本题中两个指针分别指向链表当前节点和其前驱节点,前驱节点(nodePrev)作用是方便后续节点插入链表,题目中两个链表都可以该思想;
  • 3.在遍历过程只要维护prev指针,需要做的就是调整链表的next指针;
  • 4.当 first 和 second 都不是空链表时,判断 first 和 second 哪一个链表的头节点的值更小,将较小值的节点添加到结果里,当一个节点被添加到结果里之后,将对应链表中的节点向后移一位;

1.思路

解决方法1(个人想法):

  • Step 1.创建指针first和second指针分别指向两个链表的头节点,此时first和second节点均为null,所以node1Prev = null, node2Prev = null;
  • Step 2.当first当前节点的值大于second节点的值时,就把second当前的节点接在first前驱节点node1Prev的后面,同时将second指针往后移一位(注:这里需要注意的是second第一个节点就比first第一个节点小时,那list1 = node2Prev,list1为返回的链表指针);
  • Step 3.当first当前节点值小于second时,则node1Prev指向first当前节点,first指针往后移动一位;
  • Step 4.重复2,3步骤,直到first或者second为null循环终止,当second不为null时,直接将链表list1末尾指向未合并完的链表即可;

看不懂解释的话,直接看算法图解比较容易理解点

2.复杂度分析:

时间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中,l1 和 l2 只有一个元素会被放进合并链表中, 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的,因此总的时间复杂度为 O(n+m)。。

空间复杂度:O(1)。我们只需要常数的空间存放若干变量。

3.算法图解

同时遍历两个链表(蓝色部分代表first指针,灰色部分代表second指针)(注:本人不会做成流程动画,希望会的朋友可以私信我指点一二,说个软件名字也可以,谢谢


三、代码实现

每个代码块都写了注释,方便理解,代码还可以改进;

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        else if(list2 == null) return list1;
        //把链表2有序插入到链表1中,再返回链表1的头结点
        ListNode first = list1, second = list2, node1Prev = null, node2Prev = null;
        while(second != null && first != null){
            if(second.val < first.val){
                node2Prev = second;
                second = second.next;
                // 插入节点
                addIndex(node1Prev, first, node2Prev);
                if(node1Prev == null) {
                    list1 = node2Prev;
                    node1Prev = node2Prev;
                }
                node1Prev = node2Prev;
            }else{
                node1Prev = first;
                first = first.next;    
            }
        }
        // 如果链表2没有合并完的话,接将链表末尾指向未合并完的链表即可
        if(second != null) node1Prev.next = second;
        return list1;
    }
    //参数分别为 前驱结点,当前结点,插入结点
    public void addIndex(ListNode prev, ListNode temp, ListNode index){
        if(prev == null){
            index.next = temp;
        }else{
            prev.next = index;
            index.next = temp;
        }
    }
}

提交结果:


总结

以上就是今天要讲的内容,这一题还是比较简单的,一看到这题的时候就立马想到同时遍历两个链表,然后把其中一个链表当做返回参数,让第二个链表的节点往里面插入即可。

感谢观看,如果有帮助到你,请给题解点个赞和收藏,让更多的人看到。🌹 🌹 🌹

也欢迎你,关注我。👍 👍 👍

原创不易,还希望各位大佬支持一下,你们的点赞、收藏和留言对我真的很重要!!!💕 💕 💕 最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!


相关文章
|
1天前
|
算法 索引
力扣刷题【第一期】
这是一个关于算法的总结,包含7个不同的问题。1)爬楼梯问题,使用动态规划,通过迭代找到到达n阶楼梯的不同方法数。2)两数之和,通过双重循环找出数组中和为目标值的两个数的索引。3)移动零,使用双指针将数组中的0移到末尾。4)合并有序链表,创建新链表按升序合并两个链表。5)删除链表重复值,遍历链表删除重复元素。6)环形链表检测,使用快慢指针判断链表是否有环。7)相交链表,计算链表长度找
7 1
|
2天前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
8 0
|
3天前
|
算法
[优选算法]——双指针——Leetcode——1089. 复写零
[优选算法]——双指针——Leetcode——1089. 复写零
|
3天前
|
算法
【优选算法】——双指针——Leetcode——283.移动零
【优选算法】——双指针——Leetcode——283.移动零
|
3天前
21. 合并两个有序链表
21. 合并两个有序链表
19 4
|
3天前
|
存储 搜索推荐 C语言
Leetcode—合并两个有序数组—C语言
Leetcode—合并两个有序数组—C语言
|
5天前
力扣56.合并区间
力扣56.合并区间
|
11天前
|
索引
LeetCode438题(无敌双指针——滑动窗口)
LeetCode438题(无敌双指针——滑动窗口)
|
11天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
12 0
|
3天前
|
C语言
C语言指针——练习
C语言指针——练习