Leetcode-21 —— Merge two sorted lists

Description

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

分析

合并两个有序链表,合并后的链表也应是有序的,而且重复元素不去重

假设有 a, b 两个链表,考虑以下 corner case:

  • 其中一个链表为 null
  • a 的末尾元素大于 b 的首元素
  • a 的元素个数比 b 多

常规的解法就是遍历两个列表,为新生成的链表维护一个头指针 dummyHead 和一个滑动指针cur,另外分别为两个给定的链表维护一个指针,假设为 a, b,按如下规则遍历

  1. 初始化 dummyHead 和 cur, 让 dummyHead = cur
  2. 初始化 a, b 分别指向两个链表的头节点
  3. 比较 a, b ,让小的一个节点作为 cur 的 next 节点,并且指针向后移动一位, cur 同样向后移动一位
  4. 重复 3,直到 a, b 两个指针之一为空
  5. 如果 a, b 中还有非空指针,让其作为 cur 的 next 节点
  6. 返回 dummyHead 的 next 节点

程序设计

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
/**
* 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 cur = new ListNode(0);
ListNode dummyHead = cur;

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

cur = cur.next;
}

if (l1 != null) {
cur.next = l1;
}
if (l2 != null) {
cur.next = l2;
}

return dummyHead.next;
}
}

值得注意的是,此处采用 dummyHead 作为新链表的头节点,最终返回了 dummyHead.next,这样做(比起先比较 L1 和 L2 的头节点然后选中较小者作为新链表的头节点)将特殊问题一般化,减少了特殊逻辑的处理,是很值得学习的一种思路。

如上代码,提交后运行时 0 ms, 打败 100% 的提交。

其他解法

本文标题:Leetcode-21 —— Merge two sorted lists

文章作者:Syncher

发布时间:2019年07月09日 - 18:07

最后更新:2019年07月10日 - 03:07

原始链接:https://0x400.com/2019-07-09-lc-21-merge-two-sorted-lists.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。