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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

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]

1 2 3 4

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:

1 2 3 4 5 6

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.