#36 Easy Time O(n) Space O(1) Animated

Merge Two Sorted Lists

Merge two sorted linked lists into one sorted list.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Pointer rewiring with saved next state

Before changing a link, save the only pointer that would otherwise be lost.

Approach: Dummy Node & Two Pointers

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Before changing a link, save the only pointer that would otherwise be lost.

Common Pitfall

Always store next before redirecting current.next.

Description

Merge two sorted linked lists into one sorted list.

Constraints

Time Complexity: O(n)
Space Complexity: O(1)

Solution — Dummy Node & Two Pointers

TimeO(n) SpaceO(1)

Implementation Plan

Translate the invariant into these small, testable moves.

Initialize the pointers.
Save the next node.
Rewire the current node.
Advance both pointers until the list is consumed.

def mergeTwoLists(list1, list2):
    dummy = ListNode()
    tail = dummy
    while list1 and list2:
        if list1.val <= list2.val:
            tail.next, list1 = list1, list1.next
        else:
            tail.next, list2 = list2, list2.next
        tail = tail.next
    tail.next = list1 or list2
    return dummy.next

Reverse Linked List

Reorder List

Merge Two Sorted Lists

Steps

Description

Constraints

Tags

Solution — Dummy Node & Two Pointers