Merge Two Sorted Lists

Easy · Linked List

You are given the heads of two singly linked lists, each already sorted in non-decreasing order. Combine them into a single sorted linked list by splicing together the existing nodes, and return the head of the merged list. Do not create new nodes, just relink the ones you are given so the final list is fully sorted.

Examples

Input:  list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Why:    Values from both lists are woven together so the result stays sorted.

Input:  list1 = [], list2 = []
Output: []
Why:    Both lists are empty so there is nothing to merge.

Input:  list1 = [], list2 = [0]
Output: [0]
Why:    One list is empty, so the result is simply the other list.

Constraints

0 <= length of each list <= 50, -100 <= node value <= 100, both lists are sorted in non-decreasing order

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Merge Two Sorted Lists

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Merge Two Sorted Lists. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.