Algorithm
Problem Name: 21. Merge Two Sorted Lists
Problem Link: https://leetcode.com/problems/merge-two-sorted-lists/
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = [] Output: []
Example 3:
Input: list1 = [], list2 = [0] Output: [0]
Constraints:
- The number of nodes in both lists is in the range
[0, 50]. -100 <= Node.val <= 100- Both
list1andlist2are sorted in non-decreasing order.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode head, *p;
p = &head;
while (l1 && l2) {
if (l1->val < = l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
// chain remaining
if (l1) p->next = l1;
if (l2) p->next = l2;
p = head.next;
return p;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1 || !l2) return l1 ? l1 : l2;
ListNode head(0);
ListNode* cur = &head;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
}
else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return head.next;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null || list2 == null) {
return list1 == null ? list2 : list1;
}
ListNode prev = null;
ListNode head = null;
while (list1 != null && list2 != null) {
if (list1.val < = list2.val) {
prev = list1;
if (head == null) {
head = list1;
}
list1 = list1.next;
} else {
ListNode node = list2;
list2 = list2.next;
if (prev == null) {
node.next = list1;
prev = node;
head = prev;
} else {
prev.next = node;
node.next = list1;
prev = node;
}
}
}
if (list2 != null) {
prev.next = list2;
}
if (list1 != null) {
prev.next = list1;
}
return head;
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const mergeTwoLists = function(l1, l2) {
if (l1 === null) return l2;
if (l2 === null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1: return l2
elif not l2: return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _021_MergeTwoSortedLists
{
public ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
var head = new ListNode(-1);
var current = head;
while (l1 != null && l2 != null)
{
if (l1.val < = l2.val)
{
current.next = l1;
l1 = l1.next;
}
else
{
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 == null ? l2 : l1;
return head.next;
}
}
}
Input
Output