Interview Prep Warmup: Merge Two Sorted Lists via LeetCode

This problem was originally solved on LeetCode.

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = []
Output: []

Example 3:

Input: l1 = [], l2 = [0]
Output: [0]

The Problem: LeetCode’s Merge Two Sorted Lists

Our goal here is to merge two sorted lists and then return a sorted result.

That gives us two options:

  1. Merge the two lists, and then sort the result.
  2. Merge the two lists such that the result is already sorted.

I’ve chosen the second option, sine it doesn’t require us to spend extra time sorting already-sorted lists.

How do you merge and sort two lists at once?

We can take advantage of the fact that both lists are already sorted and implement a merge sort algorithm.

In case you’re rusty:

  • Create a third list
  • Check the head of the two original lists and append the min value to the tail of the new list
  • Move the pointer to the next element in the selected list and repeat the process until you reach the end of both lists

My Solution to the Merge Two Sorted Lists Problem

Here’s my solution, it’s written in PHP and runs in O(n + m) time where n and m are the length of the original lists.

    function mergeTwoLists($l1, $l2) {
        $n1 = $l1;
        $n2 = $l2;
        $node = null;
        $merged = $node;
        $head = null;
        
        while (!empty($n1) || !empty($n2)) {
            $node = new ListNode();
            if (!empty($n1) && !empty($n2)) {
                if ($n1->val <= $n2->val) {
                    $node->val = $n1->val;
                    $n1 = $n1->next;
                } else {
                    $node->val = $n2->val;
                    $n2 = $n2->next;
                }
            } else if (!empty($n1)) { 
                $node->val = $n1->val;
                $n1 = $n1->next;
            } else {
                $node->val = $n2->val;
                    $n2 = $n2->next;
            }
            if (empty($merged)) {
                $merged = $node;
                $head = $node;
            } else {
                $merged->next = $node;
                $merged = $merged->next;
            }
        }
        
        return $head;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *