21. Merge Two Sorted Lists

EasyRecursionLinked List
Leetcode Link

Problem Description

You are given two sorted linked lists list1 and list2. Your task is to merge these two linked lists into a single sorted linked list. This new list should retain all the nodes from both list1 and list2, and it must be sorted in ascending order. The final linked list should be constructed by connecting the nodes from the two lists directly, which is similar to splicing. The function should return the new list's head node.

Intuition

The intuition behind the given solution approach comes from the fact that both list1 and list2 are already sorted. The algorithm can take advantage of this by comparing the nodes from both lists and choosing the smaller one to be the next node in the merged list. This selection process is repeated until one of the lists is exhausted.

We start by creating a dummy node, which is a typical technique used in linked list operations where the head of the result list is unknown. The dummy node acts as a non-invasive placeholder to build our solution without knowing the head in advance; after the merge operation, the actual head of the merged list will be dummy.next.

A pointer named curr is assigned to keep track of the end of the already built part of the merged list; it starts at the dummy node. We use a while loop to iterate as long as there are elements in both list1 and list2. During each iteration, we compare the values of the current heads of both lists and append the smaller node to the next of curr, moving list1 or list2 and curr forward.

When the loop ends because one of the lists is empty, we know that all the remaining elements in the non-empty list must be larger than all elements already merged because the lists were sorted initially. So, we can simply point the next of curr to the non-empty list to complete the merge. Finally, we return the actual start of the merged list, which is dummy.next.

Learn more about Recursion and Linked List patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

A heap is a ...?

Solution Approach

The solution is implemented using a simple iterative approach which traverses both input linked lists simultaneously, always taking the next smallest element to add it to the merged linked list. The main data structure used here is the singly-linked list. The algorithm employs the classic two-pointer technique to merge the lists.

Here are the step-by-step details of the algorithm:

  1. A dummy node is created; this node does not hold any meaningful value but serves as the starting point of the merged linked list.
  2. A curr pointer is initialized to point at the dummy node. This pointer moves along the new list as nodes are added.
  3. A while loop continues as long as there are elements in both list1 and list2. Inside the loop, a comparison is made:
    • If the value of the current node in list1 is less than or equal to the value of the current node in list2, the next pointer of curr is linked to the current node of list1, and list1 is advanced to its next node.
    • Otherwise, curr next is linked to the current node of list2, and list2 is advanced to its next node.
  4. After each iteration, curr is moved to its next node, effectively growing the merged list.
  5. If one of the lists is exhausted before the other, the loop ends. Since one of the lists (either list1 or list2) will be None, the or operator in Python ensures that curr.next will be linked to the remaining non-empty list.
  6. Finally, the head of the merged list, which is immediately after the dummy node, is returned (dummy.next), thus omitting the dummy node which was just a placeholder.

This algorithm provides a clean and efficient way to traverse through two sorted lists, merging them without requiring additional space for the new list, as it reuses the existing nodes from both lists. It effectively adheres to the O(n) time complexity, where n is the total number of nodes in both lists combined, because each node is visited exactly once.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Example Walkthrough

Let's consider the following small example to illustrate the solution approach. Suppose we have two linked lists:

1List1: 1 -> 3 -> 5
2List2: 2 -> 4 -> 6

We want to merge List1 and List2 into a single sorted linked list.

  1. First, we create a dummy node. It doesn't store any data but will serve as an anchor point for our new list.

  2. We initialize a curr pointer to the dummy node. This curr will be used to keep track of the last node in our merged list.

  3. Now we enter our while loop. Since both List1 and List2 have elements, we make comparisons:

    • We compare List1's head (1) with List2's head (2). Since 1 is less than 2, we link curr to List1's head and advance List1 to the next element (which makes it 3 now).

  4. The list starts to form: Dummy -> 1. Curr now moves to 1.

  5. In the next comparison, List1's value (3) is greater than List2's value (2). So we link curr to List2's head and advance List2 to the next element (which makes it 4 now).

  6. The list now is: Dummy -> 1 -> 2. Curr moves forward to 2.

  7. As we continue this process, the next comparison has List1's value (3) less than List2's value (4), so we link curr to List1's head and move List1 forward.

  8. The list now looks like: Dummy -> 1 -> 2 -> 3. Curr moves to 3.

  9. This process of comparing and moving forward continues until we reach the end of one list. In this example, the merged list sequence goes: Dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6, after exhaustively comparing:

    • 3 is less than 4
    • 5 is greater than 4
    • 5 is less than 6

  10. Since we've reached the end of List1 (there are no more elements to compare), we link curr to the remaining List2 (which is just 6 now).

  11. We've reached the end of both lists, and our merged list is: Dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6.

  12. Finally, we return dummy.next as the head of the new list, which omits the dummy node. So our final merged list is 1 -> 2 -> 3 -> 4 -> 5 -> 6.

Throughout the traversal, we only moved forward, directly connecting the smaller node from either list to the merged list, until we completely traversed both lists and combined them into one sorted list.

Solution Implementation

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5
6class Solution:
7    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
8        # Creating a sentinel node which helps to easily return the head of the merged list
9        sentinel = ListNode()
10      
11        # Current node is used to keep track of the end of the merged list
12        current = sentinel
13      
14        # Iterate while both lists have nodes
15        while list1 and list2:
16            # Choose the smaller value from either list1 or list2
17            if list1.val <= list2.val:
18                current.next = list1   # Append list1 node to merged list
19                list1 = list1.next     # Move to the next node in list1
20            else:
21                current.next = list2   # Append list2 node to merged list
22                list2 = list2.next     # Move to the next node in list2
23          
24            # Move the current pointer forward in the merged list
25            current = current.next
26      
27        # Add any remaining nodes from list1 or list2 to the merged list
28        # If one list is fully traversed, append the rest of the other list
29        current.next = list1 if list1 else list2
30      
31        # The sentinel node's next pointer points to the head of the merged list
32        return sentinel.next
33
1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5    int val;
6    ListNode next;
7
8    ListNode() {}
9
10    ListNode(int val) { this.val = val; }
11
12    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
13}
14
15public class Solution {
16
17    /**
18     * Merge two sorted linked lists and return it as a new sorted list. 
19     * The new list should be made by splicing together the nodes of the first two lists.
20     *
21     * @param list1 First sorted linked list.
22     * @param list2 Second sorted linked list.
23     * @return The head of the merged sorted linked list.
24     */
25    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
26        // Initialize a dummy node to act as the head of the merged list.
27        ListNode dummyHead = new ListNode();
28        // This pointer will be used to add new elements to the merged list.
29        ListNode current = dummyHead;
30
31        // As long as both lists have elements, keep iterating.
32        while (list1 != null && list2 != null) {
33            if (list1.val <= list2.val) { // If list1's value is less or equal, add it next.
34                current.next = list1;
35                list1 = list1.next; // Move to the next element in list1.
36            } else { // If list2's value is less, add it next.
37                current.next = list2;
38                list2 = list2.next; // Move to the next element in list2.
39            }
40            current = current.next; // Move forward in the merged list.
41        }
42
43        // In case one of the lists has remaining elements, link them to the end.
44        current.next = (list1 == null) ? list2 : list1;
45
46        // dummyHead.next points to the head of the merged list.
47        return dummyHead.next;
48    }
49}
50
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    // Merges two sorted linked lists into one sorted linked list
14    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
15        // Creates a dummy head node to facilitate easy return and manipulation of the merged list.
16        ListNode* dummyHead = new ListNode();
17        // Maintains the current node pointer in the merged list.
18        ListNode* current = dummyHead;
19      
20        // Traverse both lists while both have elements.
21        while (list1 && list2) {
22            // Compare the current values from both lists to determine which node to take next.
23            if (list1->val <= list2->val) {
24                // Take the node from list1 and advance the list1 pointer.
25                current->next = list1;
26                list1 = list1->next;
27            } else {
28                // Take the node from list2 and advance the list2 pointer.
29                current->next = list2;
30                list2 = list2->next;
31            }
32            // Advance the pointer in the merged list.
33            current = current->next;
34        }
35      
36        // Append the non-empty remainder of the list to the merged list.
37        // If list1 is not empty, append it; otherwise, append list2.
38        current->next = list1 ? list1 : list2;
39      
40        // The dummy head's next points to the start of the merged list,
41        // so return dummyHead->next.
42        return dummyHead->next;
43    }
44};
45
1// Definition for singly-linked list node
2interface ListNode {
3    val: number;            // The value of the node
4    next: ListNode | null;  // The reference to the next node
5}
6
7/**
8 * Merge two sorted linked lists and return it as a new sorted list.
9 * The new list should be made by splicing together the nodes of the first two lists.
10 * 
11 * @param list1 - The head node of the first linked list.
12 * @param list2 - The head node of the second linked list.
13 * @returns The head node of the merged linked list.
14 */
15function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
16    // If one of the lists is null, return the other list since there's nothing to merge
17    if (list1 === null || list2 === null) {
18        return list1 || list2;
19    }
20
21    // Compare the values of the two list heads and recursively merge the rest of the lists
22    if (list1.val < list2.val) {
23        // If the value of the first list head is less, 
24        // link that node to the result of merging the rest of the lists
25        list1.next = mergeTwoLists(list1.next, list2);
26        return list1;
27    } else {
28        // If the value of the second list head is less or equal,
29        // link that node to the result of merging the rest of the lists
30        list2.next = mergeTwoLists(list1, list2.next);
31        return list2;
32    }
33}
34
Not Sure What to Study? Take the 2-min Quiz：

Which of the following uses divide and conquer strategy?

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n + m), where n and m are the lengths of list1 and list2 respectively. This is because the while loop continues until we reach the end of one of the input lists and during each iteration of the loop, it processes one element from either list1 or list2. Therefore, in the worst case, the loop runs for the combined length of list1 and list2.

Space Complexity

The space complexity of the code is O(1). While we are creating a dummy node and a curr pointer, the space they use does not scale with the input size, as they are just pointers used to form the new linked list. No additional data structures are used that depend on the input size, so the space used by the algorithm does not grow with the size of the input lists.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used in a depth first search?

Recommended Readings

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫