Reverse Linked List
Given the head of a singly linked list, reverse the list and return the reversed list.
Constraints:
- The number of nodes in the list is in the range [0, 5000].
- -5000 <= Node.val <= 5000
Examples:
Input: [1,2,3,4,5]
Output: [5,4,3,2,1]
Explanation: The input list is 1 -> 2 -> 3 -> 4 -> 5. After reversing, the list becomes 5 -> 4 -> 3 -> 2 -> 1.
Solutions
Iterative Approach
Time: O(n)Space: O(1)
We initialize three pointers: prev, curr, and nextTemp. We traverse the list and for each node, we do the following: store the next node in nextTemp, reverse the link of the current node, and move the pointers one step forward.
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}Follow-up:
How would you reverse a doubly linked list?
