[LeetCode] 21. Merge Two Sorted Lists

Table of Contents

Description

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2: Input: list1 = [], list2 = []
Output: []

Example 3: Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

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

Approach

To merge two sorted linked lists, we can use a recursive approach. The idea is to compare the values of the nodes at the heads of both lists and recursively merge the smaller node with the rest of the list.

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  // If either list is null, return the other list.
  if (!list1 || !list2) return list1 || list2;

  // Compare the current nodes of both lists.
  if (list1.val < list2.val) {
    // If list1's value is smaller, recursively merge list1.next with list2.
    list1.next = mergeTwoLists(list1.next, list2);

    return list1;
  }
  // Otherwise, recursively merge list1 with list2.next.
  list2.next = mergeTwoLists(list1, list2.next);

  return list2;
};

Complexity Analysis

Time Complexity

The time complexity of this algorithm is $O(n + m)$, where n and m are the lengths of the two linked lists. This is because we traverse each node of both lists once.

Space Complexity

The space complexity is $O(n + m)$ due to the recursion stack. In the worst case, we may have to store all nodes in the recursion stack if the nodes of two lists are interleaved.