Reverse Linked List
Problem Description
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Example 2:
Example 3:
Constraints:
- The number of nodes in the list is the range
[0, 5000]. -5000 <= Node.val <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
Solve it on LeetCode
Approaches
1. Iterative Solution
Intuition:
The iterative approach involves using a loop to reverse the pointers of the linked list's nodes one by one. By starting from the head, we can keep track of the previous node and progressively change the current node's next pointer to point to this previous node. We move through the list, effectively flipping all the pointers, until the entire list is reversed.
Algorithm:
- Initialize three pointers:
prev(set tonull),curr(set tohead), andnext(to store thecurr.nextnode temporarily). - Iterate through the list:
- Store
curr.nextinnextto save the rest of the list. - Reverse the pointer of the
currnode to point toprev. - Move
prevandcurrone step forward. - Continue until
currbecomesnull. - The new head of the list is the
prevnode.
Code:
- Time Complexity: O(n) – We are iterating through the list once, where
nis the number of elements in the list. - Space Complexity: O(1) – We use only a constant amount of extra space.
2. Recursive Solution
Intuition:
The recursive approach involves diving deeper into the list until we reach the end and starting the reversal from there. As each recursive call returns, we reverse the pointers at that level. This way, the pointers are adjusted in a postfix manner.
Algorithm:
- Base Case: If
headisnullorhead.nextisnull, returnhead. This means we found the new head of the reversed list. - Recursive Case: Reverse the rest of the list and get the new head.
- Once the rest of the list is reversed, connect
head.next.nexttoheadand sethead.nexttonull. - Return the new head obtained from the recursive call.
Code:
- Time Complexity: O(n) – Each node's operation is constant, and we perform it for every node.
- Space Complexity: O(n) – The recursion stack will have
nframes, one for each node in the list.