Skip to content
LEETFLIX

Merge Two Sorted Lists

EasyLinked listRecursion
Solve on LeetCode

Easy · merge two sorted lists. Real solution for this problem — same player as the hand-authored deep-dives.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 21. Merge Two Sorted Lists. The copyrighted prompt is on LeetCode. This page is a working merge two sorted lists for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

  • —Player inputs are capped so the animation stays readable.
  • —Match LeetCode's own constraints when you submit there.

Examples

Input

l1 =
[1, 2, 4]
l2 =
[1, 3, 4]

Output

[1, 1, 2, 3, 4, 4]

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Two pointers, always take the smaller head

Both lists are already sorted. At each step emit the smaller current head and advance that list.

Same merge as in merge-sort. Because each head is the smallest remaining value on its side, the global next value is min(l1[i], l2[j]).

Algorithm

  1. Walk i on l1 and j on l2.
  2. While both remain, append the smaller value and advance that pointer.
  3. Append whatever is left on the other list.
Time
O(n + m)
Space
O(n + m)
Solution.py
class Solution:    def mergeTwoLists(self, l1: list[int], l2: list[int]) -> list[int]:        out: list[int] = []        i = j = 0        while i < len(l1) and j < len(l2):            if l1[i] <= l2[j]:                out.append(l1[i])                i += 1            else:                out.append(l2[j])                j += 1        out.extend(l1[i:])        out.extend(l2[j:])        return out
Watch this run

03

Interactive walkthrough

Playing “Two pointers, always take the smaller head”. Edit the input, hit Run, then scrub.

Approach: Two pointers, always take the smaller head

Loading animation…