Python header question from leetcode solution

[member 428835]

Hi PF!

I am looking at the following code

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

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    # Two pointers - fast and slow
    slow = head
    fast = head
    # Move fast pointer n steps ahead
    for i in range(0, n):
        if fast.next is None:
            # If n is equal to the number of nodes, delete the head node
            if i == n - 1:
                head = head.next
            return head
        fast = fast.next
    # Loop until fast node reaches to the end
    # Now we will move both slow and fast pointers
    while fast.next is not None:
        slow = slow.next
        fast = fast.next
    # Delink the nth node from last
    if slow.next is not None:
        slow.next = slow.next.next
    return head
if __name__ == "__main__" : 
    head = [1,2,3,4,5]
    n = 2
    print(removeNthFromEnd(head,n))

Can anyone tell me what the first 4 lines are doing? Also, when I execute this code I get the error

Traceback (most recent call last):
  File "a19_removeNthNode.py", line 32, in <module>
    print(removeNthFromEnd(head,n))
  File "a19_removeNthNode.py", line 13, in removeNthFromEnd
    if fast.next is None:
AttributeError: 'list' object has no attribute 'next'

Anyone know what's happening?

 

[jedishrfu]

The first four lines are creating a class called listnode that has a value and a pointer to the next listnode item. listnode is one node of a linked list.

in your program you are passing in an array object and the code is trying to treat it as a listnode. See line 27 and beyond. You need to create a listnode object from the array [,2,3,4,5] to pass into the removeNthNode()

 

[FactChecker]

Your code starting at line 27 needs to start by creating a list, one node at a time. Then it can try to remove nodes from that list.

 

[Mark44]

As already noted, this part doesn't work, starting from line 28:

head = [1,2,3,4,5]
n = 2
print(removeNthFromEnd(head,n))

The list above consists of integer values, but it needs to contain ListNode objects. You can do this by using a loop in which each iteration creates a ListNode instance, and then appends it to a list of these objects.
Be sure to set the val and next attributes for each ListNode instance. I did this using two separate loops.

 

[FactChecker]

Be sure to set the val and next attributes for each ListNode instance. I did this using two separate loops.

Because the next node does not exist when a node is first added, there is some confusion and the 'next' property can not be set. It seems as though it would be nice for a node to have a 'prior' property or to add nodes in reverse order. A 'prior' property would allow an added node to go back to the prior node and set its 'next' property. The 'prior' pointer to the latest added node would have to be saved somewhere in order to set it when another node is added.

 

[Mark44]

Because the next node does not exist when a node is first added, there is some confusion and the 'next' property can not be set.

Right, and this is why I used two loops. The first one set the val attribute for each, and set the next attribute for each to None. The next loop set the next pointers appropriately, but with the last node's next pointer remaining at None.

I thought about how this might be done using just one loop, starting from the end node. Nothing came immediately to mind, though.

 

[jedishrfu]

A recursive approach might work.

 

[member 428835]

Thank you all for the great discussion!

 

[pbuk]

Bear in mind that creating the input list is not part of the LeetCode challenge which you can see here: https://leetcode.com/problems/remove-nth-node-from-end-of-list/ - you need to select Python3 from the dropdown manually.

 

[pbuk]

I thought about how this might be done using just one loop, starting from the end node. Nothing came immediately to mind, though.

items = [1, 2, 3, 4, 5]
head = None
for value in reversed(items):
    head = ListNode(value, head)