[LC] 206. Reverse Linked ListTech
Reverse a singly linked list.
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL
A linked list can be reversed either iteratively or recursively. Could you implement both?
It is another problem I spent about 3 hours though it is in “easy” category. I’ve solved it about 20 times before but every time when I was trying to solve it, I got so much confusions.
I knew it needs three pointers: prev, curr, next. And I also knew their co-relations. However, somehow it did not work correctly and was not easy to debug.
My problem was my approach. I thought that I can write a code directly with a short thoughts. It bring me a lot of bugs. So, I wrote down every use case based on algorithm what I knew so far, and finally I realized what I’ve missed. In here, I actually need “root” as well and curr pointer should be connected with it. So, my final algorithm is:
- while curr is not null
- curr.next = root (a head node in the list)
- prev.next = next
- root = curr
- move curr to next, and assign curr = next
Here is my final solution.
class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head prev, curr, next = head, head.next, head.next.next root = head root.next = prev while curr: curr.next = root prev.next = next root=curr curr = next if not curr: break next = next.next return root
Time Complexity: O(N)
Space Complexity: O(1)
Runtime: 40 ms, faster than 39.24% of Python3 online submissions for Reverse Linked List.
Memory Usage: 15.6 MB, less than 50.50% of Python3 online submissions for Reverse Linked List.