AttributeError: 'NoneType' object has no attribute 'next'

[loves]

The question is Given the head of a linked list, remove the nth node from the end of the list and return its head.

My code:

class ListNode:
   def __init__(self, val=0, next=None):
       self.val = val
       self.next = next

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        total = 0
        temp = head
        while temp is not None:
            temp = temp.next
            total += 1
          
        
        k = total - n
        prev = None
        curr = head
        while k > 0:
            prev.next = curr
            curr = curr.next
            k -= 1
        if prev is None:
            return head.next
        else:
            prev.next = curr.next
        return head
    
list1 = ListNode(2);
list1.next = ListNode(4)
list1.next.next = ListNode(3)
list1.next.next.next = ListNode(5);
list1.next.next.next.next = ListNode(6);
list1.next.next.next.next.next = ListNode(4)
list1.next.next.next.next.next.next = ListNode(7)
s = Solution()
print(s.removeNthFromEnd(list1, 5))

But I got the error at line 19

File "C:\Code\Leetcode-python\19.py", line 19, in removeNthFromEnd
prev.next = curr

AttributeError: 'NoneType' object has no attribute 'next'

Thanks for the hint.

[deanhystad]

        prev = None
        curr = head
        while k > 0:
            prev.next = curr

You set prev = None and nearly then next thing you do is try to set prev.next = curr. But prev is None, and None (NoneType) does not have an attribute named "prev".

Are you being forced to make a linked list only using ListNode? Normally the link is a small part of a linked list, and it is often hidden behind the linked list API. If I was doing this assignment I would make a LinkedList class that had a head and a tail and a size and this kind of problem would be pretty simple to solve. My solution to this problem would be:

class Solution:
    def removeNthFromEnd(self, llist, n):
        llist.remove(len(llist)-n)
        return llist.head

print(Solution().removeNthFromEnd(LinkedList((2, 4, 3, 5, 6, 4, 7))))

[bowlofred]

If you wanted to assume the linked list was "big" (so you didn't want to copy the data), and you want to do only one pass, then you have to keep track of the last n+1 nodes. Could toss them onto a queue or a deque of size n+1.

When you reach the end, the head of the queue either has the previous node (which is the one that has to be modified), or your list is shorter and you might have a special case or two to handle.