Code Logo

Merge Two Sorted Lists

Published at25 Jul 2026
Created by
Singly Linked List Easy 0 views
Like0

Given two sorted arrays representing linked lists, merge them into one sorted array. Both input arrays are sorted in ascending order. The result should also be sorted in ascending order and contain all elements from both inputs.

For example, merging [1, 2, 4] and [1, 3, 4] produces [1, 1, 2, 3, 4, 4]. Merging an empty array with [0] produces [0]. Merging two empty arrays produces []. The merge preserves duplicate values — every element from both inputs appears in the result.

Merging two sorted lists is a foundational algorithm used in merge sort, data integration, and set operations. The two-pointer technique compares elements from both arrays and always takes the smaller one, ensuring the result stays sorted. This runs in O(m+n) time with O(m+n) space.

This is the array equivalent of merging two sorted linked lists, a classic linked list operation. In linked list form, you would compare the heads of both lists and redirect the next pointer of the result list to the smaller head, advancing that list's pointer.

Edge cases include one or both arrays being empty (return the non-empty one or empty), arrays of different lengths (the remaining elements of the longer array are appended at the end), and arrays with duplicate values across both lists (they should all appear in the result in order).

Example Input & Output

Example 1
Input
[],[],[]
Output
[]
Explanation

Both empty

Example 2
Input
[5],[1,2]
Output
[1,2,5]
Explanation

Different lengths

Example 3
Input
[],[]
Output
[1,1,2,3,4,4]
Explanation

Two sorted lists

Example 4
Input
[],[0]
Output
[0]
Explanation

One empty

Example 5
Input
[1,2],[3,4]
Output
[1,2,3,4]
Explanation

No overlap

Algorithm Flow

Recommendation Algorithm Flow for Merge Two Sorted Lists
Recommendation Algorithm Flow for Merge Two Sorted Lists

Solution Approach

Use two pointers to compare elements from both arrays, always appending the smaller one.

function solution(a, b) {
  var r = [], i = 0, j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] < b[j]) { r.push(a[i]); i++; }
    else { r.push(b[j]); j++; }
  }
  while (i < a.length) { r.push(a[i]); i++; }
  while (j < b.length) { r.push(b[j]); j++; }
  return r;
}

Initialize an empty result array and two index pointers at 0. While both arrays have elements remaining, compare the current elements and push the smaller one, advancing its pointer. After one array is exhausted, push all remaining elements from the other array.

Time complexity is O(m+n), space complexity is O(m+n) for the result.

Best Answers

java
class Solution {
    public int[] solution(int[] a, int[] b) {
        int[] r=new int[a.length+b.length];int i=0,j=0,k=0;
        while(i<a.length&&j<b.length){if(a[i]<b[j]){r[k++]=a[i++];}else{r[k++]=b[j++];}}
        while(i<a.length){r[k++]=a[i++];}while(j<b.length){r[k++]=b[j++];}return r;
    }
}