206. Reverse Linked List — LeetCode(Python)
I got you!
Problem:
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]Example 2:
Input: head = [1,2]
Output: [2,1]Example 3:
Input: head = []
Output: []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?
Solution:
1. Iterative Method—
if not head or not head.next:
return head
prev = None
curr = head
while curr:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
return prevExplanation —
We return the linked list itself if it has 0 or 1 nodes because, in that case, it tis sorted by definition.
Next, we set up two pointers — a null pointer[which later becomes our tail’s next pointer] and a pointer pointing to the current head. These prev and curr nodes represent the previous and current nodes respectively.
Now we traverse the list and perform the reversal.
A temporary variable is set and the next node is stored in it.
The curr node’s next is set to the prev node.
The prev node pointer is shifted to our curr node, so that our current node becomes the previous node in the next iteration.
And then the curr node pointer is also shifted to the next node that we had stored in temp.
Finally, prev is returned since it now stores the last element in the original linked list, and our curr pointer is null to terminate the while loop.
Time and Space Complexity —
Since we are traversing the list only once, we can say that our algorithm runs in linear time.
Also, we require a constant amount of extra space.
Thus, if n is the length of the linked list,
Time Complexity: O(n)
Space Complexity; O(1)
2. Recursive Method —
if not head or not head.next:
return head
node = self.reverseList(head.next)
head.next.next = head
head.next = None
return nodeExplanation —
The termination condition of our recursion is when we have a list of either 1 or 0 elements; in which case, we return the list itself, because it is in reverse order by definition.
The recursive step is where we call our recursive function on the remaining part of the list and store it in node.
We make the next of our head to point to our head.
And we make our head point to None.
Finally, node is returned — which stores the head of the new linked list.
Time and Space Complexity —
Since every node in the list is traversed once, we can say that our algorithm runs in linear time.
Also, since the recursion stack stores all elements in the linked list at some point, we need a linear amount of extra space.
Thus, if n is the length of the linked list,
Time Complexity: O(n)
Space Complexity: O(n)
