- What Does the Problem Say?<\/a><\/li>
- Solution 1: Brute Force Approach (Using Stack)<\/a>
- Intuition<\/a><\/li>
- Detailed Approach<\/a><\/li>
- Code<\/a><\/li>
- Code Explanation<\/a><\/li>
- Dry Run<\/a><\/li>
- Time and Space Complexity<\/a><\/li>
- Simplifying It<\/a><\/li><\/ul><\/li>
- Solution 2: Iterative Approach (Optimal)<\/a>
- Intuition<\/a><\/li>
- Detailed Approach<\/a><\/li>
- Code<\/a><\/li>
- Code Explanation<\/a><\/li>
- Dry Run<\/a><\/li>
- Time and Space Complexity<\/a><\/li>
- Simplifying It<\/a><\/li><\/ul><\/li>
- Solution 3: Recursive Approach<\/a>
- Intuition<\/a><\/li>
- Detailed Approach<\/a><\/li>
- Code<\/a><\/li>
- Code Explanation<\/a><\/li>
- Dry Run<\/a><\/li>
- Time and Space Complexity<\/a><\/li>
- Simplifying It<\/a><\/li><\/ul><\/li>
- Summary<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n
\n\n\n\nWhat Does the Problem Say?<\/h2>\n\n\n\n
Given the
head<\/code> of a singly linked list, reverse the list, and return the reversed list<\/em>.<\/p>\n\n\n\nExample 1:<\/strong><\/p>\n\n\n\n
![\"\"\/](\"https:\/\/assets.leetcode.com\/uploads\/2021\/02\/19\/rev1ex1.jpg\")
<\/figure>\n\n\n\nInput:<\/strong> head = [1,2,3,4,5]
Output:<\/strong> [5,4,3,2,1]<\/pre>\n\n\n\nExample 2:<\/strong><\/p>\n\n\n\n
![\"\"\/](\"https:\/\/assets.leetcode.com\/uploads\/2021\/02\/19\/rev1ex2.jpg\")
<\/figure>\n\n\n\nInput:<\/strong> head = [1,2]
Output:<\/strong> [2,1]<\/pre>\n\n\n\nExample 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> head = []
Output:<\/strong> []<\/pre>\n\n\n\nConstraints:<\/strong><\/p>\n\n\n\n
- \n
- The number of nodes in the list is the range
[0, 5000]<\/code>.<\/li>\n\n\n\n-5000 <= Node.val <= 5000<\/code><\/li>\n<\/ul>\n\n\n\nFollow up:<\/strong> A linked list can be reversed either iteratively or recursively. Could you implement both?<\/p>\n\n\n\n
\n\n\n\nSolution 1: Brute Force Approach (Using Stack)<\/h2>\n\n\n\n
Intuition<\/h3>\n\n\n\n
Think of this like stacking plates! When you put plates on a stack, the last plate you put becomes the first one you take out. We’ll use this same idea – store all the values in a stack, then put them back in reverse order.<\/p>\n\n\n\n
Detailed Approach<\/h3>\n\n\n\n
- \n
- First Pass<\/strong>: Walk through the entire linked list and store all node values in a stack<\/li>\n\n\n\n
- Second Pass<\/strong>: Walk through the linked list again and replace each node’s value with values popped from the stack<\/li>\n\n\n\n
- Since stack follows LIFO (Last In, First Out), we get the reverse order automatically<\/li>\n<\/ol>\n\n\n\n
Code<\/h3>\n\n\n\n
- Second Pass<\/strong>: Walk through the linked list again and replace each node’s value with values popped from the stack<\/li>\n\n\n\n
- Detailed Approach<\/a><\/li>
- Detailed Approach<\/a><\/li>
- Detailed Approach<\/a><\/li>
- Solution 1: Brute Force Approach (Using Stack)<\/a>