Merge Two Sorted Lists

easyFREELinked ListBlind 75

Write merge_lists(l1, l2) that merges two sorted lists into one sorted list and returns it as a list. Every element of both inputs must appear in the result (duplicates are kept), and either input may be empty. The tests print the returned list as space-separated values.

Example

Input

1,2,4
1,3,4

Output

1 1 2 3 4 4

Reasoning

The inputs are two lists, l1 = [1, 2, 4] and l2 = [1, 3, 4], each already in non-decreasing order. They can have different lengths, and either one can be empty.
The output holds every element from both lists exactly once, so its length is $3 + 3 = 6$ . Nothing is dropped and nothing is de-duplicated.
Count each value across the two inputs: $1$ appears once in each list, so twice in total. $2$ and $3$ appear once each, and $4$ appears once in each list, so twice. In non-decreasing order that gives $1 \le 1 \le 2 \le 3 \le 4 \le 4$ .
The function returns that list, [1, 1, 2, 3, 4, 4]. The tests print it with spaces between the values: 1 1 2 3 4 4.
Notice that when one input is empty, the result is just the other list, and two empty inputs give an empty list (printed as EMPTY).

Constraints

0 <= list length <= 50
-100 <= values <= 100
Both lists are sorted in non-decreasing order

Learn this in

FundamentalsDSA Study Plan

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The problem "Merge Two Sorted Lists" involves working with linked lists, a fundamental data structure in computer science. A linked list is a sequence of nodes, where each node contains a value and a reference (i.e., a "link") to the next node in the sequence. In this case, we're dealing with sorted linked lists, meaning that the values in each list are arranged in ascending order. To solve this problem, you should be familiar with basic linked list operations, such as traversing a list and inserting or deleting nodes.

Understanding pointers is also crucial, as they are used to reference and manipulate nodes in the linked list. In the context of linked lists, pointers are used to keep track of the current node and to move to the next node in the sequence. You should be comfortable with the concept of a head pointer, which points to the first node in the list, and a next pointer, which points to the next node in the sequence.

The problem requires merging two sorted lists into one sorted list, which involves comparing values from both lists and arranging them in the correct order. This process involves using conditional statements and loops to iterate through both lists and create a new sorted list. The output should be a space-separated list of values, which can be achieved using basic string manipulation techniques.

Algorithm/Approach

The general approach to solving this problem involves using a comparative sorting technique, where values from both lists are compared and arranged in the correct order. This can be achieved by iterating through both lists simultaneously and using a temporary pointer to keep track of the current node in the merged list. The algorithm should handle cases where one list is longer than the other and ensure that the resulting list is properly sorted.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize a new head pointer to keep track of the merged list
Compare the values of the head nodes of both lists and add the smaller value to the merged list
Move the next pointer to the next node in the list with the smaller value
Repeat the comparison and insertion process until one of the lists is exhausted
Append the remaining nodes from the non-exhausted list to the merged list
Return the head pointer of the merged list

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Forgetting to handle the case where one list is longer than the other
Not properly updating the next pointers when inserting nodes into the merged list
Failing to initialize the new head pointer correctly
Not checking for null pointers when traversing the lists

Time & Space Complexity

The expected time complexity for this problem is O(n + m), where n and m are the lengths of the two input lists. This is because we need to iterate through both lists to merge them. The space complexity is O(n + m) as well, as we need to create a new list to store the merged result.

solution.py

Python 3.13

Test results