deepSWE.io

Merge Two Sorted Lists

Linked ListTwo Pointers

15 min

Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example

Example 1:

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

List 1

List 2

Output: [1,1,2,3,4,4]

Constraints

The number of nodes in both lists is in the range [0, 50].
-100 ≤ Node.val ≤ 100
Both list1 and list2 are sorted in non-decreasing order.

Iterative Solution Walkthrough

The iterative approach merges two sorted lists by repeatedly comparing the heads of the lists and appending the smaller node to the result.

List 1

List 2

Merged List

empty

Click 'Next' to start the merge process.

Algorithm Steps

Create a dummy node to start the merged list.
Compare the nodes at the current pointers of both lists.
Append the smaller node to the merged list and advance its pointer.
Repeat until one list is empty.
Append the remaining portion of the non-empty list.

Iterative Solution


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Create a dummy node to act as the starting point of the merged list.
        dummy = ListNode()
        # 'curr' will be our pointer to build the new list.
        curr = dummy

        # Loop as long as both lists have nodes.
        while l1 and l2:
            # Compare the values of the nodes from both lists.
            if l1.val < l2.val:
                # If l1's value is smaller, link it to our merged list.
                curr.next = l1
                # Move l1's pointer forward.
                l1 = l1.next
            else:
                # Otherwise, link l2's node.
                curr.next = l2
                # Move l2's pointer forward.
                l2 = l2.next
            
            # Move our builder pointer forward.
            curr = curr.next

        # After the loop, one list may still have nodes left.
        # We can just append the remainder of whichever list is not empty.
        if l1:
            curr.next = l1
        elif l2:
            curr.next = l2
        
        # The merged list starts after the dummy node.
        return dummy.next