LeetCode-in-TypeScript.github.io

21. Merge Two Sorted Lists

Easy

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]

Output: [1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = []

Output: []

Example 3:

Input: l1 = [], l2 = [0]

Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both l1 and l2 are sorted in non-decreasing order.

Solution

import { ListNode } from '../../com_github_leetcode/listnode'

/**
 * 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(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    let list = new ListNode(-1)
    let head = list
    while (l1 !== null || l2 !== null) {
        if (l1 !== null && l2 !== null) {
            if (l1.val <= l2.val) {
                list.next = new ListNode(l1.val)
                l1 = l1.next
            } else {
                list.next = new ListNode(l2.val)
                l2 = l2.next
            }
        } else if (l1 !== null) {
            list.next = new ListNode(l1.val)
            l1 = l1.next
        } else if (l2 !== null) {
            list.next = new ListNode(l2.val)
            l2 = l2.next
        }
        list = list.next!
    }
    return head.next
}

export { mergeTwoLists }

This site is open source. Improve this page.