数据结构之链表

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

示例

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

分析

递归遍历对比链表的值, 将较小的值的next指针指向较大的

代码

Python3

def mergeTwoLinkList(self, l1, l2):
  if l1 is None:
    return l2
  if l2 is None:
    return l1
  if l1.val < l2.val:
    l1.next = self.mergeTwoLinkList(l1.next, l2)
    return l1
  else:
    l2.next = self.mergeTwoLinkList(l1, l2.next)
    return l2

JavaScript

function mergeTwoLinkList (l1, l2) {
  if (l1 === null) return l2
  if (l2 === null) return l1
  if (l1.val < l2.val) {
    l1.next = mergeTwoLinkList(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLinkList(l1, l2.next)
    return l2
  }
}