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:
def reverseList(self, head:
ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prevFollow-up:
How would you reverse a doubly linked list?
