Merge Two Sorted Lists

Try to solve the Merge Two Sorted Lists problem.

We'll cover the following

Statement#

Given the heads of two sorted linked lists, list1 and list2, merge these lists into a single sorted list. This involves integrating all the nodes from both lists while ensuring that their sorted order is preserved. Return the head of the merged linked list as the output.

Constraints:

  • 00 ≤\leq Number of nodes in both lists ≤50\leq 50

  • −100≤-100 \leq Node.data ≤100\leq 100

  • Both lists are sorted in a non-decreasing order.

Examples#

canvasAnimation-image

1 of 3

canvasAnimation-image

2 of 3

canvasAnimation-image

3 of 3

Understand the Problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Merge Two Sorted Lists

1

What is the output if the following lists are given as input?

list1list1 = 11 → 22 → 33 → nullnull

list2list2 = −1-1 → −2-2 → 33 → nullnull

A)

33 → nullnull

B)

−1-1 → −2-2 → 33 → nullnull

C)

−1-1 → −2-2 → 11 → 22 → 33 → nullnull

D)

−1-1 → −2-2 → 11 → 22 → 33 → 33 → nullnull

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Create a new linked list to store all the nodes from both input lists in a non-decreasing order.

Traverse the input lists simultaneously and compare the value of nodes pointed to by heads of the respective lists.

Among the values being compared, add the one which is smaller in the new linked list.

Once both input lists are fully traversed, return the new list which now contains all the nodes in a sorted order.

Try it yourself#

Implement your solution in main.py in the following coding playground. We have provided a few useful code templates in the other files that you may build on to solve this problem.

Python
main.py
linked_list_node.py
linked_list.py
print_list.py
Input #1
Input #2
%0 node_01 1 node_11 2 node_01->node_11 node_21 3 node_11->node_21
Visualization for Input #1
Merge Two Sorted Lists

K-way Merge: Introduction

Solution: Merge Two Sorted Lists