CosmosNing的个人博客

探索·好奇

0%

合并有序线性表

发表于 更新于 分类于
本文字数： 3.1k 阅读时长 ≈ 3 分钟
本篇文章带来有关两道有关 "合并有序线性表" 的求解过程

刷题标记

  • 第一遍
  • 第二遍
  • 第三遍
  • 第四遍
  • 第五遍

求解过程

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

示例：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

编写 public ListNode mergeTwoLists(ListNode l1, ListNode l2) 函数

思路

合并有序线性表 L1、L2，有一个通用的思路，如下

  1. 初始化每个表的遍历指针 Lp1，Lp2；并且新建一个线性表 L3，存储结果。
  2. 循环比较，将较小元素放入 L3
  3. 如果 L1 还有元素未遍历，处理 L1 剩余元素
  4. 处理 L2 剩余元素未遍历，处理 L2 剩余元素

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

    // 创建带有头指针的链表，方便操作
    ListNode l3 = new ListNode(0);
    // 新建一个 p 指针用于遍历
    ListNode p = l3;

    // 循环比较，并把较小的结点加入链表 l3
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val){
            p.next = l1;
            p = p.next;
            l1 = l1.next;
        }else{
            p.next = l2;
            p = p.next;
            l2 = l2.next;
        }
    }

    // 将 l1 剩余元素加入 l3
    if(l1 != null){
        p.next = l1;
    }

    // 将 l2 剩余元素加入 l3
    if(l2 != null){
        p.next = l2;
    }


    // 删除 l3 的头指针
    return l3.next;

}
  • 时间复杂度为 \(O(n+m)\)
  • 空间复杂度为 \(O(1)\)

高手方案

思路：递归

高手还另外提供了一种递归思路：

  • 两个链表头部较小的一个与剩下元素的 merge 操作结果合并

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    else if (l2 == null) {
        return l1;
    }
    else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }
    else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }

}
  • 时间复杂度为 \(O(n+m)\)
  • 空间复杂度为 \(O(n+m)\) ：最多消耗 n+m 层栈空间

类似题：88.merge-sorted-array

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 示例:

输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

刷题标记

  • 第一遍
  • 第二遍
  • 第三遍
  • 第四遍
  • 第五遍

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public void merge(int[] nums1, int m, int[] nums2, int n) {

    // 先把 nums 所有元素移到最后，记录开始位置
    for (int i = m - 1; i >= 0; i--) {
        nums1[i + n] = nums1[i];
    }

    // 再遍历比较，写入到 nums1 前半部分
    int k = 0;
    int i = 0, j = n;
    while (i < n && j < n + m) {
        if (nums1[j] < nums2[i]) {
            nums1[k++] = nums1[j++];
        } else {
            nums1[k++] = nums2[i++];
        }
    }

    // 处理 nums1 剩余元素
    while (j < n + m){
        nums1[k++] = nums1[j++];
    }

    // 处理 nums2 剩余元素
    while (i < n){
        nums1[k++] = nums2[i++];
    }

}
  • 时间复杂度为 \(O(n+m)\)
  • 空间复杂度为 \(O(1)\)

高手方案

  • 思路
    • 从后往前遍历，将大的放到 nums1 的指定位置
  • Java 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetcode/

public void merge(int[] nums1, int m, int[] nums2, int n) {
    // two get pointers for nums1 and nums2
    int p1 = m - 1;
    int p2 = n - 1;
    // set pointer for nums1
    int p = m + n - 1;

    // while there are still elements to compare
    while ((p1 >= 0) && (p2 >= 0))
        // compare two elements from nums1 and nums2 
        // and add the largest one in nums1 
        nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];

    // add missing elements from nums2
    System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
}
  • 时间复杂度为 \(O(n+m)\)
  • 空间复杂度为 \(O(1)\)

总结

合并有序线性表 L1、L2，有一个通用的思路，如下

  1. 初始化每个表的遍历指针 Lp1，Lp2；并且新建一个线性表 L3，存储结果。
  2. 循环比较，将较小元素放入 L3
  3. 如果 L1 还有元素未遍历，处理 L1 剩余元素
  4. 处理 L2 剩余元素未遍历，处理 L2 剩余元素