LeetCode 图解 | 21.合并两个有序链表

点击上方蓝字设为星标LeetCode 图解 | 21.合并两个有序链表

下面开始今天的学习~

LeetCode 图解 | 21.合并两个有序链表

今天分享的题目来源于 LeetCode 上第 21 号问题:合并两个有序链表。

题目描述

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

示例:

输入:1->3->4, 2->5->6
输出:1->2->3->4->5->6

题目解析

首先,设定一个虚拟节点 dummy 用来存储结果,循环对比 L1 和 L2 节点上的数字,通过调整 p节点的 next 指针来调整 dummy 的结果。

  • 如果 L1 当前位置的值小于等于 L2 ,我们就把  L1 的值接在  dummy 节点的后面同时将  L1 指针往后移一个

  • 如果 L2 当前位置的值小于 L2 ,我们就把  L2 的值接在  p 节点的后面同时将  L2 指针往后移一个

  • 不管我们将哪一个元素接在了 p 节点后面,都需要向后移一个元素

  • 重复以上过程,直到  L1 或者  L2 指向了 null 

  • 在循环终止的时候,  L1 和  L2 至多有一个是非空的。由于输入的两个链表都是有序的,所以不管哪个链表是非空的,它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面,并返回合并链表。

动画理解

代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

 //@程序员吴师兄
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), p = dummy;

    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        p.next = l1;
        l1 = l1.next;
      } else {
        p.next = l2;
        l2 = l2.next;
      }
      p = p.next;
    }

    if (l1 != null) p.next = l1;
    if (l2 != null) p.next = l2;
    return dummy.next;
    }
}

复杂度分析

时间复杂度:O(m+n),m 与 n 方便是链表的长度。每次循环迭代中,L1 和 L2只有一个元素会被放进合并链表中, while 循环的次数等于两个链表的总长度。

空间复杂度:O(1),迭代的过程只会产生几个指针,所以它所需要的空间是常数级别的。

相关题目推荐

  • LeetCode 23:合并 K 个排序链表

  • LeetCode 88:合并两个有序数组

  • LeetCode 148:排序链表

  • LeetCode 244:最短单词距离 II

LeetCode 图解 | 21.合并两个有序链表

原文始发于微信公众号(图解面试算法):LeetCode 图解 | 21.合并两个有序链表

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » LeetCode 图解 | 21.合并两个有序链表

我还会在以下平台发布内容

GitHub 哔哩哔哩