合并两个排序的链表

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

递归版

递归版详解

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

非递归版本

讨论区

  function Merge(pHead1, pHead2) {
    if (pHead1 === null) {
      return pHead2
    }
    if (pHead2 === null) {
      return pHead1
    }
    let mergeHead = null
    let current = null
    while (pHead1 !== null && pHead2 !== null) {
      if (pHead1.val <= pHead2.val) {
        if (mergeHead === null) {
          mergeHead = current = pHead1
        } else {
          current.next = pHead1
          current = current.next
        }
        pHead1 = pHead1.next
      } else {
        if (mergeHead === null) {
          mergeHead = current = pHead2
        } else {
          current.next = pHead2
          current = current.next
        }
        pHead2 = pHead2.next
      }
    }
    if (pHead1 === null) {
      current.next = pHead2
    } else {
      current.next = pHead1
    }
    return mergeHead
  }