What is the time and space complexity of Merge Two Sorted Lists?

Time complexity: O(n + m). Space complexity: O(1).

Merge Two Sorted Lists

Easy

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Merge Two Sorted Lists

Approach

Create a dummy head node and a tail pointer. Compare the heads of both lists, attach the smaller node to tail, and advance that list pointer. When one list is exhausted, append the remaining nodes of the other.

Complexity Analysis

Time: O(n + m)
Space: O(1)

Pattern

Linked List (Dummy Node + Merge)

Why It Works

Both input lists are already sorted. By always picking the smaller head node, the merged list maintains sorted order. The dummy node eliminates edge cases when the merged list is empty.

Updated Feb 2026