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)，迭代的过程只会产生几个指针，所以它所需要的空间是常数级别的。