Code Logo

Merge Two Sorted Lists

Published at25 Jul 2026
Created by
Singly Linked List Easy 1 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

Solution Approach

Merge two sorted linked lists into one sorted list. Use a dummy node and a tail pointer. Compare the heads of both lists, attach the smaller node to the tail, and advance the pointer. When one list is exhausted, attach the remainder of the other list directly.

function mergeTwoLists(l1, l2) {
  var dummy = { next: null }, tail = dummy;
  while (l1 && l2) {
    if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; }
    else { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }
  tail.next = l1 || l2;
  return dummy.next;
}

The dummy head simplifies the initial attachment. The tail pointer always points to the last node of the merged result. The final line attaches whatever remains of either list.

Time complexity is O(n + m), space complexity is O(1).

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;
    }
}