[LC] 206. Reverse Linked List
TechReverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
Approach
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.
![](https://ikwhanchang.com/wp-content/uploads/2021/02/image-13-1024x632.png)
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)
Submissions
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.