LeetCode 21: Merge Two Sorted Lists — Step-by-Step Visual Trace

Easy — Linked List | Two Pointers | Recursion | Merge

The Problem

Merge two sorted linked lists into one sorted linked list by splicing together the nodes of the first two lists.

Approach

Use a dummy node to simplify edge cases and maintain a current pointer. Compare values at the head of both lists, attach the smaller node to the result, and advance the corresponding pointer. After one list is exhausted, attach the remaining nodes from the other list.

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

Code

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        dummy = ListNode()
        current = dummy

        while list1 and list2:
            if list1.val < list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next

        if list1:
            current.next = list1
        elif list2:
            current.next = list2

        return dummy.next

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments