1, 题目

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2, 算法

  1. 第一步, 一个链表,直接返回
  2. 第二步, 建立新链表
  3. 第三步, 比较加入节点
  1. #scala
  2. object Solution {
  3.     def mergeTwoLists(l1: ListNode, l2: ListNode): ListNode = {
  4.         if (l1 == null) {
  5.             return l2
  6.         }
  7.         if (l2 == null) {
  8.             return l1
  9.         }
  10.         val head = new ListNode()
  11.         var current_node = head
  12.         var list1 = l1
  13.         var list2 = l2
  14.         while (list1 != null && list2 != null) {
  15.             if (list1.x <= list2.x) {
  16.                 current_node.next = list1
  17.                 list1 = list1.next
  18.                 current_node = current_node.next
  19.                 current_node.next = null
  20.             } else {
  21.                 current_node.next = list2
  22.                 list2 = list2.next
  23.                 current_node = current_node.next
  24.                 current_node.next = null
  25.             }
  26.         }
  27.         if (list1 != null) {
  28.             current_node.next = list1
  29.         }
  30.         if (list2 != null) {
  31.             current_node.next = list2
  32.         }
  33.         head.next
  34.     }
  35. }
#python
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        head = ListNode()
        current_node = head
        while l1 and l2:
            if l1.val <= l2.val:
                current_node.next = l1
                l1 = l1.next
                current_node = current_node.next
                current_node.next = None
            else:
                current_node.next = l2
                l2 = l2.next
                current_node = current_node.next
                current_node.next = None
        if l1:
            current_node.next = l1
        if l2:
            current_node.next = l2
        return head.next