DEV Community

Cover image for LeetCode Meditations: Merge Two Sorted Lists
Eda
Eda

Posted on • Originally published at rivea0.github.io

LeetCode Meditations: Merge Two Sorted Lists

The description for Merge Two Sorted Lists says:

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

Merge the two lists into 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.

For example:

Example for merging two sorted lists

mergeTwoLists([1, 2, 4], [1, 3, 4]);
// -> [1, 1, 2, 3, 4, 4]


mergeTwoLists([], []);
// -> []


mergeTwoLists([], [0]);
// -> [0]
Enter fullscreen mode Exit fullscreen mode

First, let's think about how we would do it with a simple array. We would have two pointers: one for the first array, and the other for the second.
As we iterate through them both simultaneously, we'd get the smaller value in our result array. At the end of the iteration, if there are some more elements left in one of the arrays (in case of different lengths), we'd simply add them all as well.

Let's write a pseudocode of how we would go about doing it:

i = 0
j = 0
result = []

while i < arr1.length and j < arr2.length:
    if arr1[i] < arr2[j]:
        add arr1[i] to result
        i = i + 1
    else:
        add arr2[j] to result
        j = j + 1

while i < arr1.length:
    add arr1[i] to result
    i = i + 1

while j < arr2.length:
    add arr2[j] to result
    j = j + 1
Enter fullscreen mode Exit fullscreen mode

The solution for this problem looks very similar, only difference is that we'll do it with a linked list. Let's look at it in TypeScript:

/**
 * 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 {
  // Start with an initial node with value 0
  let result = new ListNode(0);
  let currentNode = result;

  while (list1 !== null && list2 !== null) {
    if (list1.val < list2.val) {
      currentNode.next = list1;
      list1 = list1.next;
    } else {
      currentNode.next = list2;
      list2 = list2.next;
    }

    currentNode = currentNode.next;
  }

  if (list1 !== null) {
    currentNode.next = list1;
  }

  if (list2 !== null) {
    currentNode.next = list2;
  }

  // Go past the first dummy value of 0
  return result.next;
}
Enter fullscreen mode Exit fullscreen mode

We initialize result with a node that holds the value of 0. We'll also keep a pointer to currentNode that initially points to the head of result.
As we traverse the lists, we'll link the smaller value first by pointing currentNode's next pointer to that value.

If, at the end, we haven't finished looking at all the nodes in one of the lists (in case of different lengths), we'll simply link the rest of it.

To return, we need to go past the first initial dummy node with the value 0, so we'll return result.next which starts with the actual value that we added from one of the lists. And, we're done.

Time and space complexity

The time complexity is O(m+n)O(m + n) —where mm is the length of the first list, and nn is the length of the second list— because we need to "touch" each node in each list once.

The space complexity is O(n)O(n) because of the result list we hold: its size will grow with the input size.


Next up is a slightly more challenging problem called Reorder List. Until then, happy coding.

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

This post blew up on DEV in 2020:

js visualized

🚀⚙️ JavaScript Visualized: the JavaScript Engine

As JavaScript devs, we usually don't have to deal with compilers ourselves. However, it's definitely good to know the basics of the JavaScript engine and see how it handles our human-friendly JS code, and turns it into something machines understand! 🥳

Happy coding!

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay