11

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

 4 years ago
source link: https://www.cxyxiaowu.com/8334.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
LeetCode 图解 | 21.合并两个有序链表-五分钟学算法
当前位置：五分钟学算法 > LeetCodeAnimation > 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.合并两个有序链表


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK