Merge Two Sorted Lists - Practice Coding Problems

Merge Two Sorted Lists - Problem

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.

Input & Output

Example 1 — Basic Merge

$ Input: list1 = [1,2,4], list2 = [1,3,4]

› Output: [1,1,2,3,4,4]

💡 Note: Merge by comparison: 1≤1 (choose list1), 2<3 (choose list1), 3<4 (choose list2), 4≤4 (choose list1), then 4 from list2

Example 2 — One Empty List

$ Input: list1 = [], list2 = [0]

› Output: [0]

💡 Note: When one list is empty, return the other list directly

Example 3 — Both Empty

$ Input: list1 = [], list2 = []

› Output: []

💡 Note: When both lists are empty, return empty list

Constraints

The number of nodes in both lists is in the range [0, 50].
-100 ≤ Node.val ≤ 100
Both list1 and list2 are sorted in non-decreasing order.

Visualization

Tap to expand

Understanding the Visualization

Input

Two sorted linked lists: [1,2,4] and [1,3,4]

Process

Compare nodes and choose smaller values

Output

Single merged sorted list: [1,1,2,3,4,4]

Key Takeaway

🎯 Key Insight: Use two pointers to compare current nodes and build merged list in one pass

Asked in

a Amazon 87 M Microsoft 45 🍎 Apple 32 G Google 28

The key insight is that since both lists are already sorted, we can merge them in one pass by comparing current nodes. The two-pointer approach is optimal with Time: O(m + n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers Merge	O(m + n)	O(1)	Compare nodes from both lists and merge in one pass
Brute Force - Collect and Sort	O(n log n)	O(n)	Extract all values, sort them, create new linked list

Two Pointers Merge — Algorithm Steps

Step 1: Create dummy node to simplify edge cases
Step 2: Compare current nodes from both lists
Step 3: Choose smaller node and advance that pointer
Step 4: Attach remaining nodes from non-empty list

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Pointers

Set pointers to head of both lists and create dummy node

Compare and Choose

Compare current nodes and choose smaller one

Attach Remaining

When one list ends, attach the remaining nodes

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = NULL;
    struct ListNode* current = dummy;
    
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            current->next = list1;
            list1 = list1->next;
        } else {
            current->next = list2;
            list2 = list2->next;
        }
        current = current->next;
    }
    
    current->next = list1 ? list1 : list2;
    
    struct ListNode* result = dummy->next;
    free(dummy);
    return result;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        current = current->next;
        current->val = arr[i];
        current->next = NULL;
    }
    return head;
}

void printList(struct ListNode* head) {
    printf("[");
    int first = 1;
    while (head) {
        if (!first) printf(",");
        printf("%d", head->val);
        first = 0;
        head = head->next;
    }
    printf("]\n");
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int arr1[100], size1 = 0;
    if (strcmp(line, "[]") != 0) {
        char* token = strtok(line + 1, ",]");
        while (token) {
            arr1[size1++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int arr2[100], size2 = 0;
    if (strcmp(line, "[]") != 0) {
        char* token = strtok(line + 1, ",]");
        while (token) {
            arr2[size2++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    struct ListNode* list1 = arrayToList(arr1, size1);
    struct ListNode* list2 = arrayToList(arr2, size2);
    
    struct ListNode* result = solution(list1, list2);
    printList(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m + n)

Visit each node exactly once from both lists

✓ Linear Growth

Space Complexity

O(1)

Only uses a few pointer variables, no extra data structures

✓ Linear Space

180.3K Views

Very High Frequency

~15 min Avg. Time

8.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers Merge — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler