This content originally appeared on DEV Community and was authored by we_are_broken_compilers
Welcome back to our DSA Learning Series — where we pick one problem at a time, understand its logic deeply, and write clean, beginner-friendly Java code.
The problem that we are going to discuss today is a classic in linked lists — Merge Two Sorted Lists
It is a foundational question that not only strengthens your understanding of linked list traversal but also acts as the building block for more advanced problems like Merge K Sorted Lists, which we will explore in the next article.
Problem Statement
We are given two sorted linked lists. Our task is to merge them into a single sorted linked list.
Example:
Input:
List1: 1 → 3 → 5
List2: 2 → 4 → 6
Output:
1 → 2 → 3 → 4 → 5 → 6
Intuition
The idea is simple — both lists are already sorted. So we can use two pointers to traverse them by always picking the smaller value first and then continue until one list finishes, and then ultimately attach the remaining part of the other list.
🧱 Step 1: Iterative Approach
In this approach, we use a dummy node to simplify pointer handling. This dummy node helps us build the final list step by step without worrying about the head pointer separately.
Code
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(); // this is the dummy node to start the merged list
ListNode pointer = dummy; // this pointer is used to build the new list
while(list1 != null && list2 != null) {
if(list1.val < list2.val) {
pointer.next = list1; // attach the smaller node
list1 = list1.next; // move list 1 pointer ahead
} else {
pointer.next = list2;
list2 = list2.next; // move list 2 pointer ahead
}
pointer = pointer.next; // move result pointer ahead
}
// attach the remaining nodes
if(list1 == null) {
pointer.next = list2;
} else {
pointer.next = list1;
}
return dummy.next; // finally return the merged list formed at dummy's next
}
}
Step-by-Step Example
Let’s merge the below two lists:
List1 = 1 → 3 → 5
List2 = 2 → 4 → 6
| Step | list1 | list2 | Chosen Node | Merged List So Far |
|---|---|---|---|---|
| 1 | 1 | 2 | 1 | 1 |
| 2 | 3 | 2 | 2 | 1 → 2 |
| 3 | 3 | 4 | 3 | 1 → 2 → 3 |
| 4 | 5 | 4 | 4 | 1 → 2 → 3 → 4 |
| 5 | 5 | 6 | 5 | 1 → 2 → 3 → 4 → 5 |
| 6 | null | 6 | 6 | 1 → 2 → 3 → 4 → 5 → 6 |
🌀 Step 2: Recursive Approach
Code
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val <= l2.val) {
l1.next = mergeTwoLists(l2, l1.next);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
How the above approach works:
- The smaller node between
l1andl2becomes part of the merged list. - The function then recursively merges the rest of the nodes.
- The recursion continues until one list is empty.
This version is clean and expressive, though it uses extra call stack space (O(n + m) in the worst case).
Complexity Analysis
As each node is processed exactly once, the time complexity will be O(n + m), where n and m are the sizes of corresponding lists.
Regarding the space complexity, it is constant for iterative solution - O(1). However recursive solution adds the stack space resulting in O(n + m)
Final thoughts
This problem teaches one of the most important linked list patterns — merging while maintaining order.
It forms the foundation for more advanced problems like Merge K Sorted Lists, which we will discuss in the next article by following a Divide and Conquer approach.
💬 Your Turn:
Try implementing both iterative and recursive versions yourself. and let us know which one feels more intuitive to you — pointer manipulation or recursion?
Stay tuned and keep practicing!
This content originally appeared on DEV Community and was authored by we_are_broken_compilers
we_are_broken_compilers | Sciencx (2025-10-26T09:40:16+00:00) Merge Two Sorted Linked Lists. Retrieved from https://www.scien.cx/2025/10/26/merge-two-sorted-linked-lists/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.