The problem Merge Two Sorted Lists on LeetCode involves merging two sorted linked lists into a single sorted linked list. It’s a common problem that tests your understanding of linked lists and basic merging algorithms.
Problem Statement: Merge two sorted linked lists, l1 and l2, into a new sorted linked list and return its head. A sorted linked list is a linked list in which the nodes are arranged in ascending order based on their values.
l1: 1 -> 2 -> 4
l2: 1 -> 3 -> 4
merged: 1 -> 1 -> 2 -> 3 -> 4 -> 4One possible way to solve this problem is to use a recursive approach. This involves comparing the values of the two list heads and choosing the smaller one as the new head of the merged list. Then, we recursively merge the remaining lists and attach them to the new head. This way, we can build the merged list from the smallest to the largest node.
#include <iostream>
using namespace std;
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
// base cases: if one of the lists is empty, return the other one
if (list1 == nullptr) return list2;
if (list2 == nullptr) return list1;
// compare the values of the two list heads and choose the smaller one as the new head
ListNode* newHead = nullptr;
if (list1->val < list2->val) {
newHead = list1; // list1 has the smaller head
// recursively merge the remaining lists and attach them to the new head
newHead->next = mergeTwoLists(list1->next, list2);
} else {
newHead = list2; // list2 has the smaller head
// recursively merge the remaining lists and attach them to the new head
newHead->next = mergeTwoLists(list1, list2->next);
}
// return the new head of the merged list
return newHead;
}Time complexity: O(n + m), where n and m are the lengths of the two lists. This is because we need to traverse both lists once to merge them, and the recursive calls will take O(1) time each.
Space complexity: O(n + m), where n and m are the lengths of the two lists. This is because the recursive calls will take O(n + m) stack space in the worst case.