题目

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

方法

方法：迭代法，递归法
时间复杂度：m + n

递归法

思路

通过从小到大的顺序合并两个链表，从两个链表的头指针p1，p2开始，以两个头指针中小的那个作为新的头指针newHead，假设这里是p1较小，p1作为newHead
接下来newHead的next可能是原来的p1.next，也可能是p2，需要再次做对比，所以将p1.next和p2传入递归函数，将较小值返回
以此类推，做递归处理。当p1或者p2，某个链表已经到达尾结点null的时候，直接返回另一个链表的剩余部分，相当于直接将剩余节点接上

代码

function Merge(pHead1, pHead2) {
  // write code here
  if (!pHead1) return pHead2
  if (!pHead2) return pHead1
  
  let newHead
  if (pHead1.val < pHead2.val) {
    newHead = pHead1
    newHead.next = Merge(pHead1.next, pHead2)
  } else {
    newHead = pHead2
    newHead.next = Merge(pHead1, pHead2.next)
  }
  return newHead
}

迭代法

思路

迭代法和递归法的思路类似，只是在对比完某两个节点后，通过white循环进入下一次比较即可

代码

function Merge(pHead1, pHead2) {
  // write code here
  if (!pHead1) return pHead2
  if (!pHead2) return pHead1
  let newHead = new ListNode()
  let p = newHead
  while (pHead1 && pHead2) {
    if (pHead1.val < pHead2.val) {
      p.next = pHead1
      pHead1 = pHead1.next
    } else {
      p.next = pHead2
      pHead2 = pHead2.next
    }
    p = p.next
  }
  if (pHead1) p.next = pHead1
  if (pHead2) p.next = pHead2
  return newHead.next
}