# [LC] 206. Reverse Linked List

Example:

```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?

## 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.

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:

1. while curr is not null
1. curr.next = root (a head node in the list)
2. prev.next = next
3. root = curr
4. move curr to next, and assign curr = next

Here is my final solution.

``````class Solution:
def reverseList(self, head: ListNode) -> ListNode:
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.