šŸ”— LeetCode

Merge Two Sorted Lists

Easytwo pointersAmazonMicrosoft

Merge two sorted linked lists and return it as a new sorted list.

Examples

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

Constraints

    šŸ’” Hints

    Hint 1

    Use a dummy node.

    Algorithm Complexity

    Official asymptotic Big-O runtime and auxiliary memory analysis

    Linear
    Algorithmic Approach

    Two pointers comparing values.

    Time ComplexityO(N+M)
    Why:

    Splices nodes by comparing list1 and list2 heads, advancing one node per comparison until all N + M nodes are linked.

    Space ComplexityO(1)
    Why:

    Re-links existing ListNode pointers in-place using a dummy head, requiring O(1) auxiliary memory.

    Big-O Growth CurveLinear (O(N))
    Execution time scales directly in proportion to the input size.

    šŸ” Dry Run

    Solutionā± O(N+M) | šŸ’¾ O(1)
    currā†“
    -1
    list1ā†“
    1
    2
    list2ā†“
    1
    3