Solution: Merge Two Sorted Lists

Let's solve the Merge Two Sorted Lists problem.

We'll cover the following

Statement

Given two integer lists, nums1 and nums2, of size mm and nn, respectively, sorted in nondecreasing order. Merge nums1 and nums2 into a single list sorted in nondecreasing order.

Constraints:

  • 0≤m,n≤2000\leq m, n \leq 200

  • 1≤m+n≤2001\leq m + n \leq 200

  • −103≤-10^3 \leq nums1[i] , nums2[i] ≤103\leq 10^3

Solution 1: Creating a new list and using three pointers

Since we have two lists, nums1 and nums2, to merge, we start by creating a new empty list result of length equal to the sum of the length of nums1 and nums2. This list will be filled with all the elements of both lists in sorted order and returned. The following are the further steps of the algorithm:

  1. Initialize three pointers, p1, p2, and p3, pointing to the start of nums1, nums2, and result, respectively.

  2. Traverse both lists until the end of either nums1 and nums2 is reached.

  3. While traversing, compare the elements of nums1 and nums2, pointed by p1 and p2, respectively. Check whether the element pointed by p1 or p2 is smaller.

    1. If the element pointed by p1 is smaller, store this element at the position pointed by p3. Also, increment p1 and p3 by 1.

    2. Otherwise, if the element pointed by p2 is smaller, store this element at the position pointed by p3. Also, increment p2 and p3 by 1.

  4. After the traversal, append the rest of the elements in any of the lists to result.

The following illustrations demonstrate the algorithm:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.