4

Leetcode 21 合并两个有序链表

 3 years ago
source link: https://segmentfault.com/a/1190000040551991
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 合并两个有序链表

发布于 8 分钟前

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

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

输入：l1 = [], l2 = []
输出：[]

输入：l1 = [], l2 = [0]
输出：[0]

从链表头开始比较，l1 与 l2 是有序递增的，所以比较 l1.val 与 l2.val 的较小值就是合并后链表的最小值，次小值就是小节点的 next.val 与大节点的 val 比较的较小值，依次递归，直到递归到 l1 、l2 均为 null 。

当递归到任意链表为 null ，直接将 next 指向另外的链表即可，不需要继续递归了。

function mergeTwoLists(l1, l2) {
  if (l1 == null) return l2;
  if (l2 == null) return l1;

  if (l1.val <= l2.val) {
    // 如果 l1.val <= l2.val ，次小值就是 l1.next 与 l2 比较的较小值
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    // 如果 l1.val > l2.val ，次小值就是 l2.next 与 l1 比较的较小值
    l2.next = mergeTwoLists(l2.next, l1);
    return l2;
  }
};

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK