Merge two sorted lists
The problem
Given the heads of two linked lists, list1 and list2, where each linked list has its elements sorted in non-decreasing order, merge them into a single sorted linked list and return the head of the merged linked list.
Input: list1 = head -> 2 -> 4 -> 7 -> 9, list2 = head -> 1 -> 2 -> 5 -> 6 Output: head -> 1 -> 2 -> 2 -> 4 -> 5 -> 6 ->7 -> 9 Explanation: head -> 1 -> 2 -> 2 -> 4 -> 5 -> 6 ->7 -> 9, the underlined nodes come from list2, the others come from list1.
Input: list1 = head -> 1 -> 2 -> 3 -> 4, list2 = head -> 5 -> 6 -> 10 Output: head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 10 Explanation: head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 10, the underlined nodes come from list2, the others come from list1.
Input: list1 = head -> 0 -> 2, list2 = head -> 1 -> 3 -> 5 -> 6
- 0 <= number of nodes in list1, list2 <= 5 * 104
- -104 <= ListNode.val <= 104
- list1 and list2 are sorted in non-decreasing order.
cpp
// Definition of singly linked list:
// struct ListNode
// {
// int val;
// ListNode *next;
// ListNode(int data1)
// {
// val = data1;
// next = NULL;
// }
// ListNode(int data1, ListNode *next1)
// {
// val = data1;
// next = next1;
// }
// };
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
}
};java
/*Definition of singly linked list:
class ListNode {
int val;
ListNode next;
ListNode() {
val = 0;
next = null;
}
ListNode(int data1) {
val = data1;
next = null;
}
ListNode(int data1, ListNode next1) {
val = data1;
next = next1;
}
}
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
}
}python
# Definition of singly linked list:
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1, list2):javascript
/*Definition of singly linked list:
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
*/
class Solution {
mergeTwoLists(list1, list2) {
}
}csharp
/* Definition for singly-linked list.
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
*/
public class Solution {
public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
}
}go
// Definition of singly linked list:
// type ListNode struct {
// Val int
// Next *ListNode
// }
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
}Stuck? Show a way to structure it+
- 01Use a dummy head and tail pointer.
- 02Attach the smaller current node each step.
- 03Advance only the list that supplied it.
- 04Append the remaining suffix.
Reference answer
Then expect these follow-ups
How would you merge k sorted lists?
Tests: heap design
What changes if inputs must remain unmodified?
Tests: copying tradeoff
Hiring now
Software engineer roles are open right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland

Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India

Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY
Next question
- Calculate the trapped rainwater between bars in a given array.
- Find a triplet in an array with a given sum.
- Print all combinations of numbers from 1 to n that sum to n.
- Find the number of rotations in a circularly sorted array.
- Find all permutations of a given string.
- Check if two given binary trees are identical.