合并两个有序链表

力扣🔗：https://leetcode-cn.com/problems/valid-parentheses (opens new window)

题目

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

示例 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 均按 非递减顺序 排列

解题思路

• 首先创建一个虚拟节点，以方便后续合并操作，设置一个临时变量 temp 指向当前操作的节点。

• 整体思路是分别在 l1 和 l2 两链表中设置两个指针分别指向各自的头节点，这里沿用了变量 l1 和 l2，随后向各自的下一个节点移动，直到其中一个指针达到其链表尾部。每次移动时对比两指针指向节点的值，根据大小关系作如下处理：

  • 当 l1.val === l2.val 时，创建两个值相同的连续节点并拼接上 temp，并移动 temp 到下一个节点，移动两指针到各自的下一个节点。
  • 当 l1.val !== l2.val 时，取较小的节点值以创建新节点，拼接上 temp，移动值指向较小的节点的指针到下一个节点。
  • 移动 temp 到下一个节点。

• 检查当前两个指针指向的节点是否是尾节点，如不是则拼接上 temp 节点。

代码实现

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
function mergeTwoLists(l1, l2) {
  const result = new ListNode()
  let temp = result

  while (l1 && l2) {
    if (l1.val === l2.val) {
      // 两个节点值相等
      temp.next = new ListNode(l1.val, new ListNode(l1.val))
      temp = temp.next // 跳到下个节点

      // 同时向后移动
      l1 = l1.next
      l2 = l2.next
    } else if (l1.val > l2.val) {
      // 当前节点值较小的链表向后移动
      temp.next = new ListNode(l2.val)
      l2 = l2.next
    } else {
      temp.next = new ListNode(l1.val)
      l1 = l1.next
    }

    temp = temp.next || new ListNode() // 更新到下一个节点
  }

  temp.next = l1 || l2 // 如果有剩余节点，则添加
  return result.next
}