Description

算法步骤

尾插法

• 创建一个虚拟头节点，然后遍历两个链表，谁小谁就插到新链表的后面。
• 当两个链表其中一个遍历完成，则把另一个链表剩余的节点直接插到新链表的后面。

/**
 * 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 dummy = new ListNode(-1, null);
  let tail = dummy;
  let l1 = list1;
  let l2 = list2;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      tail.next = l1;
      l1 = l1.next;
    }
    else {
      tail.next = l2;
      l2 = l2.next;
    }

    tail = tail.next;
  }

  tail.next = l1 ?? l2;

  return dummy.next;
};
Copy