← All questions
EasyCoding

Merge two sorted lists

Asked atIntuitOracle
1Give yourself 5 minutes
2Answer out loud, not in your head
3Then compare with the answer below

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 {

}
Solve on LeetCode →
Stuck? Show a way to structure it+
  1. 01Use a dummy head and tail pointer.
  2. 02Attach the smaller current node each step.
  3. 03Advance only the list that supplied it.
  4. 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

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with EnzoSign up free

Next question