Merge Two Sorted Lists

January 10, 2024

Problem #

Given two sorted linked lists, merge them into one sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example:

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

Solution #

The solution involves using a two-pointer technique. Create a new linked list and add nodes to it by comparing the current nodes of the two lists, advancing the pointer of the list with the smaller current node.

Algorithm Steps #

1. Initialize a dummy node to act as the start of the new list.
2. Use two pointers, each pointing to the head of one list.
3. Compare the values at these pointers, add the smaller one to the new list, and advance the pointer in that list.
4. Repeat the process until one of the lists is exhausted.
5. Append the remaining elements of the non-exhausted list to the new list.
6. Return the head of the merged list (next node of the dummy node).

Code (Python) #

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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 if list1 else list2
    return dummy.next

Time Complexity #

The time complexity is O(n + m), where n and m are the lengths of the two lists, since each node in both lists is visited at most once.

Space Complexity #

The space complexity is O(1), as the solution only requires a constant amount of space for pointers and does not allocate any additional nodes.