8000 P-21 "Merge Two Sorted Lists" problem · aditya-2k23/Leetcode@d0622bb · GitHub
[go: up one dir, main page]
Skip to content

Commit d0622bb

Browse files
aditya-2k23aditya-2k23
committed
P-21 "Merge Two Sorted Lists" problem
Adds a new directory with a detailed problem description, solution approaches (iterative, recursive, and brute force), and complexity analysis. Implements the solution in C++ with three methods and a test suite to validate correctness.
1 parent dd066e9 commit d0622bb

File tree

4 files changed

+268
-2
lines changed

4 files changed

+268
-2
lines changed

‎README.md

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
[![GitHub](https://img.shields.io/badge/Repository-blue?logo=github)](https://github.com/aditya-2k23/leetcode)
44
[![License](https://img.shields.io/badge/LICENSE-MIT-yellow?logo=license.svg)](https://github.com/aditya-2k23/leetcode/blob/main/LICENSE)
5-
![Problems Solved](https://img.shields.io/badge/Solved-7-brightgreen) <!-- Update this count as you solve more problems -->
5+
![Problems Solved](https://img.shields.io/badge/Solved-8-brightgreen) <!-- Update this count as you solve more problems -->
66
![Language](https://img.shields.io/badge/Language-Python%20%7C%20Java%20%7C%20C++-orange)
77
[![Wiki](https://img.shields.io/badge/Wiki-Available-blueviolet)](https://github.com/aditya-2k23/leetcode/wiki)
88
[![Discussions](https://img.shields.io/badge/Discussions-Open-blue)](https://github.com/aditya-2k23/leetcode/discussions)
@@ -25,6 +25,7 @@ Below is a list of problems solved in this repository:
2525
- [Problem 13: Roman to Integer](problems/P-13-roman-to-integer)
2626
- [Problem 14: Longest Common Prefix](problems/P-14-longest-common-prefix)
2727
- [Problem 20: Valid Parentheses](problems/P-20-valid-parentheses)
28+
- [Problem 21: Merge Two Sorted Lists](problems/P-21-merge-two-sorted-lists)
2829
- [Problem 35: Search Insert Position](problems/P-35-search-insert-position)
2930
- _(Add more problems as they are solved)_
3031

@@ -39,7 +40,7 @@ This repository serves as my personal learning journey through algorithmic probl
3940

4041
## Directory Structure
4142

42-
- Each problem is organized in a folder named `P-<number>-<name>` (e.g., `P-1-two-sum`).
43+
- Each problem is organized in a folder named `P-<number>-<name>` (e.g., [`P-1-two-sum`](problems/P-1-two-sum)).
4344
- Inside each problem folder:
4445
- `README.md`: Problem description, approach, and complexity analysis.
4546
- `solution.<extension>`: Solution code in a specific programming language (e.g., `solution.py` for Python).

‎problems/P-21-merge-two-sorted-lists/README.md

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
# Problem 21: Merge Two Sorted Lists
2+
3+
- **Difficulty**: Easy
4+
- **Topics**: Linked List, Recursion
5+
- **LeetCode Link**: [Problem URL](https://leetcode.com/problems/merge-two-sorted-lists/)
6+
7+
## Problem Description
8+
9+
You are given the heads of two sorted linked lists list1 and list2.
10+
11+
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
12+
13+
Return the head of the merged linked list.
14+
15+
**Example 1:**
16+
![ex:1 image](https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg)
17+
18+
**Input:** `list1 = [1,2,4], list2 = [1,3,4]`
19+
**Output:** `[1,1,2,3,4,4]`
20+
21+
**Example 2:**
22+
**Input:** `list1 = [], list2 = []`
23+
**Output:** `[]`
24+
25+
**Example 3:**
26+
**Input:** `list1 = [], list2 = [0]`
27+
**Output:** `[0]`
28+
29+
**Constraints:**
30+
31+
- The number of nodes in both lists is in the range `[0, 50]`.
32+
- `-100 <= Node.val <= 100`
33+
- Both `list1` and `list2` are sorted in **non-decreasing** order.
34+
35+
## Approach
36+
37+
So, there are 3 approaches to solve this problem:
38+
39+
1. **Iterative Approach**: Use a dummy node to simplify the merging process and iterate through both lists.
40+
2. **Recursive Approach**: Recursively merge the two lists by comparing their head nodes.
41+
3. **Using a vector/array**: Convert both linked lists to arrays, merge the arrays, and convert back to a linked list.
42+
43+
### Steps (Iterative Approach)
44+
45+
1. Create a dummy node to simplify the merging process.
46+
2. Use a pointer to track the current position in the merged list.
47+
3. Compare the values of the nodes in both lists and append the smaller one to the merged list.
48+
4. Move the pointer in the list from which the node was taken.
49+
5. Continue until one of the lists is exhausted.
50+
6. Append the remaining nodes of the other list to the merged list.
51+
7. Return the next node of the dummy node as the head of the merged list.
52+
53+
#### Complexity Analysis (Iterative Approach)
54+
55+
- **Time Complexity**: `O(n + m)`, where `n` and `m` are the lengths of the two lists.
56+
- **Space Complexity**: `O(1)` for the iterative approach (excluding the space used by the input lists).
57+
58+
### Steps (Recursive Approach)
59+
60+
1. If one of the lists is empty, return the other list.
61+
2. Compare the head nodes of both lists.
62+
3. Recursively merge the lists by choosing the smaller head node.
63+
4. Set the next pointer of the chosen node to the result of merging the remaining nodes.
64+
65+
#### Complexity Analysis (Recursive Approach)
66+
67+
- **Time Complexity**: `O(n + m)`, where `n` and `m` are the lengths of the two lists.
68+
- **Space Complexity**: `O(n + m)` due to the recursion stack.
69+
70+
### Steps (Using a vector/array)
71+
72+
1. Convert both linked lists to arrays.
73+
2. Merge the two arrays.
74+
3. Convert the merged array back to a linked list.
75+
76+
#### Complexity Analysis (Using a vector/array)
77+
78+
- **Time Complexity**: `O(n + m)`, where `n` and `m` are the lengths of the two lists.
79+
- **Space Complexity**: `O(n + m)` for storing the merged array.
80+
81+
## Solution
82+
83+
- **Language**: C++
84+
- **File**: [solution.cpp](solution.cpp)
85+
86+
## Test Cases
87+
88+
See the [`tests`](./tests/) folder for various test cases.
89+
90+
### Running Tests
91+
92+
- **C++ (Simple)**: `cd tests; g++ test.cpp ../solution.cpp -o test; ./test`
93+
- **Python**: `cd tests; python test.py`
94+
- **Java**: `javac .\solution.java tests/test.java; java -cp ".;tests" test`
95+
96+
---
97+
98+
> **Solved on**: 31/05/2025 |
99+
> **Time taken**: 00:35:34 |
100+
> **Attempts**: 6

‎problems/P-21-merge-two-sorted-lists/solution.cpp

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
/*
2+
* LeetCode Problem: 21. Merge Two Sorted Lists
3+
* Difficulty: Easy
4+
* Topics: Linked List, Recursion
5+
* Date Solved: 31/05/2025
6+
*/
7+
8+
#include <bits/stdc++.h>
9+
using namespace std;
10+
11+
class ListNode {
12+
public:
13+
int val;
14+
ListNode* next;
15+
ListNode(int x) : val(x), next(nullptr) {}
16+
ListNode(int x, ListNode* next) : val(x), next(next) {}
17+
};
18+
19+
class Solution {
20+
public:
21+
// Iterative method using a dummy List
22+
ListNode* iterativeMerge(ListNode* list1, ListNode* list2) {
23+
if (!list1 && !list2) return nullptr;
24+
25+
ListNode dummy(0);
26+
ListNode* tail = &dummy;
27+
28+
while (list1 && list2) {
29+
if (list1->val < list2->val) {
30+
tail->next = list1;
31+
list1 = list1->next;
32+
}
33+
else {
34+
tail->next = list2;
35+
list2 = list2->next;
36+
}
37+
tail = tail->next;
38+
}
39+
40+
tail->next = list1 ? list1 : list2;
41+
42+
return dummy.next;
43+
}
44+
45+
// Recursive method
46+
ListNode* recursiveMerge(ListNode* list1, ListNode* list2) {
47+
if (!list1) return list2;
48+
if (!list2) return list1;
49+
50+
if (list1->val < list2->val) {
51+
list1->next = recursiveMerge(list1->next, list2);
52+
return list1;
53+
}
54+
else {
55+
list2->next = recursiveMerge(list1, list2->next);
56+
return list2;
57+
}
58+
}
59+
60+
61+
// Brute Force method using a vector/array
62+
ListNode* bruteForceMerge(ListNode* list1, ListNode* list2) {
63+
if (!list1 && !list2) return nullptr;
64+
65+
vector<int> arr;
66+
while (list1) {
67+
arr.push_back(list1->val);
68+
list1 = list1->next;
69+
}
70+
71+
while (list2) {
72+
arr.push_back(list2->val);
73+
list2 = list2->next;
74+
}
75+
76+
sort(arr.begin(), arr.end());
77+
78+
ListNode* head = new ListNode(0);
79+
ListNode* temp = head;
80+
81+
for (int i : arr) {
82+
temp->next = new ListNode(i);
83+
temp = temp->next;
84+
}
85+
86+
return head->next;
87+
}
88+
};

‎problems/P-21-merge-two-sorted-lists/tests/test.cpp

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
#include "../solution.cpp"
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
vector<int> toVector(ListNode* head) {
6+
vector<int> result;
7+
while (head) {
8+
result.push_back(head->val);
9+
head = head->next;
10+
}
11+
return result;
12+
}
13+
14+
ListNode* fromVector(const vector<int>& vals) {
15+
ListNode dummy(0);
16+
ListNode* curr = &dummy;
17+
for (int v : vals) {
18+
curr->next = new ListNode(v);
19+
curr = curr->next;
20+
}
21+
return dummy.next;
22+
}
23+
24+
void printResult(const vector<int>& result) {
25+
cout << "[";
26+
for (size_t i = 0; i < result.size(); ++i) {
27+
cout << result[i];
28+
if (i < result.size() - 1) cout << ",";
29+
}
30+
cout << "]";
31+
}
32+
33+
bool testFunction(const vector<int>& input1, const vector<int>& input2, const vector<int>& expected, int testNumber) {
34+
Solution sol;
35+
ListNode* l1 = fromVector(input1);
36+
ListNode* l2 = fromVector(input2);
37+
38+
ListNode* merged = sol.iterativeMerge(l1, l2);
39+
// ListNode* merged = sol.recursiveMerge(l1, l2);
40+
// ListNode* merged = sol.bruteForceMerge(l1, l2);
41+
42+
vector<int> result = toVector(merged);
43+
cout << "Test Case " << testNumber << ": ";
44+
cout << "Input1: "; printResult(input1); cout << " ";
45+
cout << "Input2: "; printResult(input2); cout << " ";
46+
if (input1.size() < 2 && input2.size() < 2) cout << "\t";
47+
cout << "\tExpected: "; printResult(expected); cout << " Got: "; printResult(result);
48+
if (result == expected) {
49+
if (input1.size() < 2 && input2.size() < 2) cout << "\t\t\t";
50+
cout << "\tPassed\n";
51+
return true;
52+
}
53+
else {
54+
cout << "\tFailed\n";
55+
return false;
56+
}
57+
}
58+
59+
void runTests() {
60+
int passed = 0, total = 0;
61+
62+
if (testFunction({ 1,2,4 }, { 1,3,4 }, { 1,1,2,3,4,4 }, ++total)) passed++;
63+
if (testFunction({}, {}, {}, ++total)) passed++;
64+
if (testFunction({}, { 0 }, { 0 }, ++total)) passed++;
65+
if (testFunction({ 2,5,7 }, { 1,3,6,8 }, { 1,2,3,5,6,7,8 }, ++total)) passed++;
66+
if (testFunction({ -3,0,2 }, { -2,1,3 }, { -3,-2,0,1,2,3 }, ++total)) passed++;
67+
68+
cout << "\nTest Results: " << passed << "/" << total << " passed.\n";
69+
70+
if (passed == total) cout << "All tests passed successfully!\n";
71+
else cout << "Some tests failed. Please check the output for details.\n";
72+
}
73+
74+
int main() {
75+
runTests();
76+
return 0;
77+
}

0 commit comments

Comments
 (0)
0