Skip to content

21. 合并两个有序链表

21. 合并两个有序链表

代码

javascript
// 21. 合并两个有序链表:https://leetcode.cn/problems/merge-two-sorted-lists/description/
// 输入:l1 = [1,2,4], l2 = [1,3,4]
// 输出:[1,1,2,3,4,4]

import { ListNodeJs } from "../../utilsJs"

export function mergeTwoLists (list1, list2) {
  const head = new ListNodeJs(0)
  let main = head
  while (list1 && list2) {
    if (list1?.val < list2?.val) {
      main.next = list1
      list1 = list1.next
    } else {
      main.next = list2
      list2 = list2.next
    }
    main = main.next
  }
  if (list1) main.next = list1
  if (list2) main.next = list2
  return head.next
}
typescript
// 21. 合并两个有序链表:https://leetcode.cn/problems/merge-two-sorted-lists/description/
// 输入:l1 = [1,2,4], l2 = [1,3,4]
// 输出:[1,1,2,3,4,4]

import { ListNode } from "../../utils"

export function mergeTwoLists (list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const head = new ListNode(0)
  let main = head
  while (list1 && list2) {
    if (list1?.val < list2?.val) {
      main.next = list1
      list1 = list1.next
    } else {
      main.next = list2
      list2 = list2.next
    }
    main = main.next
  }
  if (list1) main.next = list1
  if (list2) main.next = list2
  return head.next
}

测试代码

ts
import { expect, test } from 'vitest'
import { mergeTwoLists } from './typescript.ts'
import { mergeTwoLists as mergeTwoListsJs } from './javascript.js'
import { getListNode } from '../../../src/utils/ListNode.ts'

const l1 = [1,2,4]
const l2 = [1,3,4]
const l3 = [1,1,2,3,4,4]
const l1ListNode = getListNode(l1)
const l2ListNode = getListNode(l2)
const l3ListNode = getListNode(l3)

test(`mergeTwoLists`, () => {
  expect(mergeTwoLists(l1ListNode, l2ListNode)).toEqual(l3ListNode)
})

const l4 = []
const l5 = [0]
const l6 = [0]
const l4ListNode = getListNode(l4)
const l5ListNode = getListNode(l5)
const l6ListNode = getListNode(l6)

test(`mergeTwoListsJs`, () => {
  expect(mergeTwoListsJs(l4ListNode, l5ListNode)).toEqual(l6ListNode)
})