#替换空格

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

#解题思路

题目信息：有序，非递减顺序，节点数目范围是 [0, 50]，拼接

#思路一

遍历两个链表的同时复用节点创造一个新链表，如果剩余则全部接上，复杂度 O(m+n)

#首次代码

function replaceSpace(s: string): string {
  return s.replaceAll(' ', '%20')
}

#代码优化

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null,
): ListNode | null {
  const newList = new ListNode()
  let l1 = list1
  let l2 = list2
  let n = newList
  let count1 = 100

  while (l1 && l2 && count1--) {
    if (l1.val > l2.val) {
      n.next = l2
      l2 = l2.next
    } else {
      n.next = l1
      l1 = l1.next
    }
    n = n.next
  }

  if (l1) {
    n.next = l1
  }

  if (l2) {
    n.next = l2
  }

  return newList.next
}