题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

提示：

• 0 <= 链表长度 <= 1000

测试用例

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

思路

最后返回的是新链表pHead，node来遍历新链表，整体流程如下：

如果 pHead1 和pHead2，均没遍历完：

• pHead1.val <= pHead2.val， node 的 next 指向 pHead1。移动 pHead1 指针。
• pHead1.val > pHead2.val， node 的 next 指向 pHead2，移动 pHead2 指针。
• node = node.next

如果一个链表遍历结束，结束循环：

• 如果 pHead1 未遍历完，node 的 next 指向 pHead1
• 如果 pHead2 未遍历玩，node 的 next 指向 pHead2

最后返回phead即可

时间复杂度是 O(N)，空间复杂度是 O(1)

代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

function ListNode(val) {
  this.val = val;
  this.next = null;
}

// 输入
var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入l1: ");
var arr1 = readline().split(",").map(Number);

console.log("请输入l2: ");
var arr2 = readline().split(",").map(Number);

// 输入的arr1转为链表
var l1 = new ListNode(-1);
var cur1 = l1;

for (let i of arr1) {
  cur1.next = new ListNode(i);
  cur1 = cur1.next;
}

// 输入的arr2转为链表

var l2 = new ListNode(-1);
var cur2 = l2;

for (let i of arr2) {
  cur2.next = new ListNode(i);
  cur2 = cur2.next;
}

var mergeTwoLists = function (l1, l2) {
  // head用来返回链表

  if (!l1) {
    return l2;
  }
  if (!l2) {
    return l1;
  }

  // 虚拟头结点
  var head = new ListNode(-1);
  var cur = head;

  // 只要有一个遍历完就跳出循环
  while (l1 && l2) {
    // l2小
    if (l1.val >= l2.val) {
      cur.next = l2;
      l2 = l2.next;
    } else {
      cur.next = l1;
      l1 = l1.next;
    }
    cur = cur.next;
  }
  // 如果l1结束了
  if (!l1) {
    cur.next = l2;
  }
  if (!l2) {
    cur.next = l1;
  }

  return head.next;
};

var res = mergeTwoLists(l1.next, l2.next);

// 数组形式输出

var ans = [];

while (res) {
  ans.push(res.val);
  res = res.next;
}

console.log("结果为: ", ans);