[LC] 206. Reverse Linked List


Reverse a singly linked list.


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?


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

            curr = next
            if not curr:
            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.

Leave a Reply

Your email address will not be published. Required fields are marked *