Reversing a linked list in python: What is wrong in my code?

Question

I am trying to reverse a linked list in python. Below is my code which doesn't work (gives an error of 'NoneType' object has no attribute 'next' at the while statement):

class Solution:
    def reverseList(self,  head: Optional[ListNode]) -> Optional[ListNode]:
        currentNode = head
        previousNode=None
        while currentNode.next is not None:
            temp=currentNode.next
            currentNode.next=previousNode
            previousNode=currentNode
            currentNode=temp
        
        currentNode.next=previousNode
        return currentNode

In my mind, what I am trying to do is that when it reaches the last node in the list (the one with next being None), it exits the while loop, and then out of the loop points, point that last node to the previous and return it as the head of the reversed list.

What is wrong in the above code and how can I fix it?

Answer 1

Here:

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

we can see that head is either an instance of ListNode or None. After the next line:

currentNode = head

we know that currentNode too is either a ListNode or None.

Then, when you check the condition:

while currentNode.next is not None:

... currentNode can be None, and None.next doesn't exist and gives an error.

Luckily, if you look at the code, currentNode will not be a None at any time after the first loop. (Why? Because it gets the old value of currentNode.next, which we know isn't None because in that case the loop would have ended.)

So the only thing you need to care about is head being None, since that is the only time you can get the error.

head is None means the list is empty, and the reverse of an empty list is still empty, so you can insert:

if head is None:
    return None

at the top of your reverseList method, and that should work just fine.