Menu
Solve LeetCode problem Merge Two Sorted Lists

Solve LeetCode problem Merge Two Sorted Lists

In this blog, we will solve the LeetCode problem Merge Two Sorted Lists.

Problem Overview

The problem is to merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists. In simple sense, we have to merge two sorted linked lists into a single sorted linked list. For example, if the input lists are:

1list1 = 1 -> 2 -> 4
2list2 = 1 -> 3 -> 4
3

4sortedList = 1 -> 1 -> 2 -> 3 -> 4 -> 4

Video Explanation

You can find the video explanation of this problem on my YouTube channel:

Approach

We can solve this problem using a simple iterative approach. We will create a new linked list and keep adding the smaller node from the two input lists to the new list. We will keep track of the tail of the new list and keep adding the smaller node to the tail. Once we reach the end of one of the input lists, we will add the remaining nodes of the other list to the new list.

The algorithm can be summarized as follows:

  • Create a new linked list to store the merged list.

    • Initialize the new linked list with a dummy node in order to avoid handling the edge case of an empty list.
    • Initialize a tail pointer to the dummy node.
    • Initialize two pointers, first and second, to the heads of the input lists.

  • Iterate through the input lists until one of the pointers reaches the end.

    • Compare the values of the first and second pointers.

      • Store the smaller node's next pointer in a temporary variable.
      • Set the smaller node's next pointer to null.
      • Set the tail's next pointer to the smaller node.
      • Move the tail pointer to the smaller node.

    • Move the tail pointer to its next node.

  • If first is null and second is not null, set the tail's next pointer to the second pointer.

  • If second is null and first is not null, set the tail's next pointer to the first pointer.

  • Return the next node of the dummy node.

Solution

1var mergeTwoLists = function (list1, list2) {
2    let newList = new ListNode(false) // dummy node
3

4    let tail = newList
5    let first = list1
6    let second = list2
7

8    while (first && second) {
9        // compare the values of the first and second pointers
10        if (first.val < second.val) {
11            let temp = first.next
12            first.next = null // Remove the link to the next node
13            tail.next = first // Add the smaller node to the new list
14            first = temp
15        } else {
16            let temp = second.next
17            second.next = null // Remove the link to the next node
18            tail.next = second // Add the smaller node to the new list
19            second = temp
20        }
21

22        tail = tail.next // Update the tail pointer
23    }
24

25    // Add the remaining nodes of the input lists to the new list
26    if (!first && second) {
27        tail.next = second
28    }
29    if (first && !second) {
30        tail.next = first
31    }
32

33    return newList.next
34}

Shameless Plug

I have made an Xbox landing page clone with React and Styled components. I hope you will enjoy it. Please consider like this video and subscribe to my channel.

That's it for this blog. I have tried to explain things simply. If you get stuck, you can ask me questions.

Contacts

Blogs you might want to read:

Videos might you might want to watch:

Next PostSolve LeetCode problem Reverse Linked List