[LC] 206. Reverse Linked List

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

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