描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

题解：

这道题目比较简单，主要考察链表的基本操作，借助虚拟头节点，遍历链表节点。将符合条件的节点不断追加到后面。

这道题目最终返回一个合并后的链表。

// 构造函数
function ListNode(x){
  this.val = x;
  this.next = null;
}
function Merge(pHead1, pHead2) {
  // 创建一个虚拟头节点 在最后新的链表 生成之后，需要借助这个指针来移动
  let dummy = new ListNode(-1)
  // 将当前的指针赋值给 cur 变量，真正移动的是它
  let cur = dummy  
  // 循环的条件是 两个链表的全部不为空
  // 针对为空的部分在最后单独处理
  while(pHead1 !== null && pHead2 !== null) {
    if(pHead1.val < pHead2.val) {
      cur.next = pHead1
      pHead1 = pHead1.next
    } else {
      cur.next = pHead2
      pHead2 = pHead2.next
    }
    // 当前移动指针
    cur = cur.next
  }
  // 处理长度不等的情况，将剩余的部分放在最后
  cur.next = pHead1 || pHead2
  // 返回新链表的头节点
  return dummy.next
}
module.exports = {
  Merge : Merge
};

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。