8000 P-206-reverse-linked-list · aditya-2k23/Leetcode@718eb5f · GitHub
[go: up one dir, main page]
Skip to content

Commit 718eb5f

Browse files
aditya-2k23aditya-2k23
committed
P-206-reverse-linked-list
Implements iterative and recursive solutions for reversing a singly linked list in C++ and Python, including explanations and complexity analysis. Adds detailed test cases for both implementations to ensure correctness across various scenarios. Provides a README with problem description, examples, approaches, and instructions for running tests in multiple languages.
1 parent ceaaf7c commit 718eb5f

File tree

6 files changed

+365
-2
lines changed

6 files changed

+365
-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-13-brightgreen) <!-- Update this count as you solve more problems -->
5+
![Problems Solved](https://img.shields.io/badge/Solved-14-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)
@@ -30,6 +30,7 @@ Below is a list of problems solved in this repository:
3030
- [Problem 27: Remove Element](problems/P-27-remove-element)
3131
- [Problem 35: Search Insert Position](problems/P-35-search-insert-position)
3232
- [Problem 88: Merge Sorted Array](problems/P-88-merge-sorted-array)
33+
- [Problem 206: Reverse Linked List](problems/P-206-reverse-linked-list)
3334
- [Problem 704: Binary Search](problems/P-704-binary-search)
3435
- [Problem 744: Find Smallest Letter Greater Than Target](problems/P-744-find-smallest-letter-greater-than-target)
3536
- _(Add more problems as they are solved)_
@@ -100,4 +101,4 @@ This project is licensed under the MIT License. See the [LICENSE](LICENSE) file
100101

101102
Happy coding! 🚀
102103

103-
> _Last updated: June 6, 2025_
104+
> _Last updated: June 7, 2025_

‎problems/P-206-reverse-linked-list/README.md

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
# Problem 206: Reverse Linked List
2+
3+
- **Difficulty**: Easy
4+
- **Topics**: Linked List, Recursion
5+
- **LeetCode Link**: [Problem URL](https://leetcode.com/problems/reverse-linked-list/)
6+
7+
## Problem Description
8+
9+
Given the `head` of a singly linked list, reverse the list, and return _the reversed list_.
10+
11+
**Example 1:**
12+
13+
![Reverse Linked List Example 1](https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg)
14+
15+
> **Input:** head = [1,2,3,4,5]
16+
> **Output:** [5,4,3,2,1]
17+
18+
**Example 2:**
19+
20+
![Reverse Linked List Example 2](https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg)
21+
22+
> **Input:** head = [1,2]
23+
> **Output:** [2,1]
24+
25+
**Example 3:**
26+
27+
> **Input:** head = []
28+
> **Output:** []
29+
30+
**Constraints:**
31+
32+
- The number of nodes in the list is in the range `[0, 5000]`.
33+
- `-5000 <= Node.val <= 5000`
34+
35+
**Follow-up:** A linked list can be reversed either iteratively or recursively. Could you implement both?
36+
37+
## Approach
38+
39+
### Iterative Approach (3 Pointers)
40+
41+
To reverse a linked list iteratively, we can use three pointers: `prev`, `current`, and `next`. The idea is to traverse the list and reverse the direction of the `next` pointer for each node.
42+
43+
### Steps
44+
45+
1. Initialize `prev` to `null`, `current` to `head`, and `next` to `null`.
46+
2. Iterate through the list:
47+
- Store the `next` node (`current.next`).
48+
- Reverse the `current.next` pointer to point to `prev`.
49+
- Move `prev` to `current`.
50+
- Move `current` to `next`.
51+
3. Continue until `current` becomes `null`.
52+
4. Finally, return `prev` as the new head of the reversed list.
53+
54+
### Recursive Approach
55+
56+
To reverse a linked list recursively, we can use the call stack to reverse the pointers. The base case is when we reach the end of the list (i.e., when `head` is `null`). We then reverse the pointers as we return from the recursive calls.
57+
58+
### Steps (Use 1 pointer front)
59+
60+
1. If `head` is `null` or `head.next` is `null`, return `head`.
61+
2. Recursively call the function with `head.next`.
62+
3. Set `front` to `head.next`.
63+
4. Set `front.next` to `head`.
64+
5. Set `head.next` to `null`.
65+
6. Return the new head of the reversed list.
66+
67+
## Solution
68+
69+
- **Language**: C++ (Iterative)
70+
- **File**: [solution.cpp](solution.cpp)
71+
72+
##
73+
74+
- **Language**: Python (Recursive)
75+
- **File**: [solution.py](solution.py)
76+
77+
## Notes
78+
79+
Reversing a linked list is a common problem that can be solved using both iterative and recursive methods. The iterative method is generally more space-efficient, while the recursive method is often more elegant and easier to understand.
80+
81+
### Complexity Analysis (Iterative)
82+
83+
- **Time Complexity**: `O(n)` where `n` is the number of nodes in the linked list.
84+
- **Space Complexity**: `O(1)` for the iterative approach (in-place reversal).
85+
86+
### Complexity Analysis (Recursive)
87+
88+
- **Time Complexity**: `O(n)` where `n` is the number of nodes in the linked list.
89+
- **Space Complexity**: `O(n)` for the recursive approach due to the call stack.
90+
91+
## Test Cases
92+
93+
See the [`tests` directory](./tests/) for various test cases implemented in C++ and Python.
94+
95+
### Running Tests
96+
97+
- **C++ (Simple)**: `cd tests; g++ test.cpp ../solution.cpp -o test; ./test`
98+
- **Python**: `cd tests; python test.py`
99+
- **Java**: `javac .\solution.java tests/test.java; java -cp ".;tests" test`
100+
101+
---
102+
103+
## Visualize the Iterative Approach
104+
105+
![Visualize](https://static.takeuforward.org/wp/uploads/2023/12/ll-reverse-a2-s2-897x1024.jpg)
106+
107+
## Visualize the Recursive Approach
108+
109+
![Visualize](https://static.takeuforward.org/wp/uploads/2023/12/Screenshot-2023-12-01-at-10.18.26-PM-1024x421.png)
110+
111+
---
112+
113+
> **Solved on**: 07/06/2025 |
114+
> **Time taken**: 00:11:17 |
115+
> **Attempts**: 3

‎problems/P-206-reverse-linked-list/solution.cpp

Lines changed: 34 additions & 0 deletions
20
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/*
2+
* LeetCode Problem: 206. Reverse Linked List
3+
* Difficulty: Easy
4+
* Topics: Linked List, Recursion
5+
* Date Solved: 07/06/2025
6+
*/
7+
8+
#include <bits/stdc++.h>
9+
using namespace std;
10+
11+
struct ListNode {
12+
int val;
13+
ListNode* next;
14+
ListNode(int x) : val(x), next(nullptr) {}
15+
};
16+
17+
class Solution {
18+
public:
19+
ListNode* reverseList(ListNode* head) {
+
if (!head || !head->next) return head;
21+
22+
ListNode* prev = nullptr;
23+
ListNode* temp = head;
24+
25+
while (temp) {
26+
ListNode* front = temp->next;
27+
temp->next = prev;
28+
prev = temp;
29+
temp = front;
30+
}
31+
32+
return prev;
33+
}
34+
};

‎problems/P-206-reverse-linked-list/solution.py

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
"""
2+
LeetCode Problem: 206. Reverse Linked List
3+
Difficulty: Easy
4+
Topics: Linked List, Recursion
5+
Date Solved: 07/06/2025
6+
"""
7+
8+
from typing import Optional
9+
10+
class ListNode:
11+
def __init__(self, val=0, next=None):
12+
self.val = val
13+
self.next = next
14+
15+
class Solution:
16+
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
17+
if not head or not head.next:
18+
return head
19+
20+
new_head = self.reverseList(head.next)
21+
22+
front = head.next
23+
front.next = head
24+
head.next = None
25+
26+
return new_head

‎problems/P-206-reverse-linked-list/tests/test.cpp

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
#include "../solution.cpp"
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
// Helper to create a linked list from vector
6+
ListNode* createList(const vector<int>& vals) {
7+
ListNode* head = nullptr;
8+
ListNode* tail = nullptr;
9+
for (int v : vals) {
10+
ListNode* node = new ListNode(v);
11+
if (!head) {
12+
head = node;
13+
tail = node;
14+
}
15+
else {
16+
tail->next = node;
17+
tail = node;
18+
}
19+
}
20+
return head;
21+
}
22+
23+
// Helper to convert linked list to vector
24+
vector<int> listToVector(ListNode* head) {
25+
vector<int> vals;
26+
while (head) {
27+
vals.push_back(head->val);
28+
head = head->next;
29+
}
30+
return vals;
31+
}
32+
33+
// Helper to print vector
34+
void printResult(const vector<int>& result) {
35+
cout << "[";
36+
for (size_t i = 0; i < result.size(); ++i) {
37+
cout << result[i];
38+
if (i < result.size() - 1) cout << ",";
39+
}
40+
cout << "]";
41+
}
42+
43+
// Helper to free linked list
44+
void freeList(ListNode* head) {
45+
while (head) {
46+
ListNode* tmp = head;
47+
head = head->next;
48+
delete tmp;
49+
}
50+
}
51+
52+
// Test function for Solution::reverseList
53+
bool testFunction(const vector<int>& input, const vector<int>& expected, int testNumber) {
54+
Solution sol;
55+
ListNode* head = createList(input);
56+
ListNode* reversed = sol.reverseList(head);
57+
vector<int> result = listToVector(reversed);
58+
59+
cout << "Test Case " << testNumber << ": Input: ";
60+
printResult(input);
61+
cout << "\t\tOutput:";
62+
if (result == expected) {
63+
printResult(result);
64+
cout << "\tExpected: ";
65+
printResult(expected);
66+
cout << "\t\tPassed\n";
67+
freeList(reversed);
68+
return true;
69+
}
70+
else {
71+
cout << "Failed: Expected ";
72+
printResult(expected);
73+
cout << ", Got ";
74+
printResult(result);
75+
cout << "\n";
76+
freeList(reversed);
77+
return false;
78+
}
79+
}
80+
81+
void runTests() {
82+
int passed = 0, total = 0;
83+
// Example 1
84+
if (testFunction({ 1,2,3,4,5 }, { 5,4,3,2,1 }, ++total)) passed++;
85+
// Example 2
86+
if (testFunction({ 1,2 }, { 2,1 }, ++total)) passed++;
87+
// Example 3 (empty list)
88+
if (testFunction({}, {}, ++total)) passed++;
89+
// Single node
90+
if (testFunction({ 42 }, { 42 }, ++total)) passed++;
91+
// Two nodes
92+
if (testFunction({ -1,0 }, { 0,-1 }, ++total)) passed++;
93+
// Negative values
94+
if (testFunction({ -3,-2,-1 }, { -1,-2,-3 }, ++total)) passed++;
95+
// Mixed values
96+
if (testFunction({ 5,-1,3,2 }, { 2,3,-1,5 }, ++total)) passed++;
97+
// Large list
98+
if (testFunction({ 1,2,3,4,5,6,7,8,9,10 }, { 10,9,8,7,6,5,4,3,2,1 }, ++total)) passed++;
99+
100+
cout << "\nTest Results: " << passed << "/" << total << " passed.\n";
101+
if (passed == total) cout << "All tests passed!\n";
102+
else cout << "Some tests failed.\n";
103+
}
104+
105+
int main() {
106+
runTests();
107+
return 0;
108+
}

‎problems/P-206-reverse-linked-list/tests/test.py

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
import sys
2+
import os
3+
# Add the parent directory to the system path
4+
sys.path.append(os.path.abspath(os.path.join(os.path.dirname(__file__), '..')))
5+
6+
from solution import Solution, ListNode
7+
8+
# Helper to create a linked list from list
9+
10+
def create_list(vals):
11+
head = None
12+
tail = None
13+
for v in vals:
14+
node = ListNode(v)
15+
if not head:
16+
head = node
17+
tail = node
18+
else:
19+
tail.next = node
20+
tail = node
21+
return head
22+
23+
# Helper to convert linked list to list
24+
def list_to_list(head):
25+
vals = []
26+
while head:
27+
vals.append(head.val)
28+
head = head.next
29+
return vals
30+
31+
# Test function for Solution.reverseList
32+
def test_function(input_list, expected, test_number):
33+
sol = Solution()
34+
head = create_list(input_list)
35+
reversed_head = sol.reverseList(head)
36+
result = list_to_list(reversed_head)
37+
print(f"Test Case {test_number}: Input: {input_list}\tOutput:", end='')
38+
if result == expected:
39+
print(f"{result}\tExpected: {expected}\tPassed")
40+
return True
41+
else:
42+
print(f"Failed: Expected {expected}, Got {result}")
43+
return False
44+
45+
def run_tests():
46+
passed = 0
47+
total = 0
48+
# Example 1
49+
if test_function([1,2,3,4,5], [5,4,3,2,1], total+1): passed += 1
50+
total += 1
51+
# Example 2
52+
if test_function([1,2], [2,1], total+1): passed += 1
53+
total += 1
54+
# Example 3 (empty list)
55+
if test_function([], [], total+1): passed += 1
56+
total += 1
57+
# Single node
58+
if test_function([42], [42], total+1): passed += 1
59+
total += 1
60+
# Two nodes
61+
if test_function([-1,0], [0,-1], total+1): < A02E span class=pl-s1>passed += 1
62+
total += 1
63+
# Negative values
64+
if test_function([-3,-2,-1], [-1,-2,-3], total+1): passed += 1
65+
total += 1
66+
# Mixed values
67+
if test_function([5,-1,3,2], [2,3,-1,5], total+1): passed += 1
68+
total += 1
69+
# Large list
70+
if test_function([1,2,3,4,5,6,7,8,9,10], [10,9,8,7,6,5,4,3,2,1], total+1): passed += 1
71+
total += 1
72+
print(f"\nTest Results: {passed}/{total} passed.")
73+
if passed == total:
74+
print("All tests passed!")
75+
else:
76+
print("Some tests failed.")
77+
78+
if __name__ == "__main__":
79+
run_tests()

0 commit comments

Comments
 (0)
0