Not able to assign head after reversing a linked list iteratively in Python

Question

I'm new to Data Structures and I was trying to reverse a linked list iteratively in Python. Below is the code.

class Node:

    def __init__(self, initval=None,next_val=None):
        self.value = initval
        self.next = next_val


    def isempty(self):
        return self.value == None

    def append(self, val):
        if self.isempty():
            self.value=val

        elif self.next==None:
            self.next=Node(val)
            
        else:
            self.next.append(val)
        return
    def insert(self, val):
        if self.isempty():
            self.value = val
            return

        newnode = Node(val)

        self.value, newnode.value = newnode.value, self.value
        self.next, newnode.next = newnode, self.next
        return
    def delete(self, val):
        if self.isempty():
            return

        if self.value == val:
            if self.next ==None:
                self.value=None

            else:
                self.value=self.next.value
                self.next=self.next.next
                return
        else:
            if self.next !=None:
                self.next.delete(val)
                if self.next.value==None:
                    self.next=None
        return
 
    def reverse(self):
        prev = None
        current = self

        while current:
            next=current.next
            current.next=prev
            prev=current
            current=next
            
        #print(prev)
        return prev
        

##    def __iter__(self):
##        node = self
##        while node !=None:
##            yield node.value
##            node=node.next
    def __str__(self):
        llist=[]
        if self.value==None:
            return str(llist)
        tmp =self
        llist.append(tmp.value)
        while tmp.next !=None:
            tmp = tmp.next
            llist.append(tmp.value)
        return str(llist)
        
def main():

    l=Node()

    for i in [2,7,6,1,4,8,9]:
        l.append(i)

    print(l,id(l))

    print(l.reverse())
    
    print(l,id(l))



if __name__ == "__main__": main()

For now this program returning only first element of reversed list. This was the output.

[2, 7, 6, 1, 4, 8, 9] 47566384
[9, 8, 4, 1, 6, 7, 2]
[2] 47566384

What I was expecting was :

[2, 7, 6, 1, 4, 8, 9] 47566384
[9, 8, 4, 1, 6, 7, 2]
[9, 8, 4, 1, 6, 7, 2] 47566384

What i tried, assigning self.value = prev in the end of reverse function outside while loop. Then I'm getting a node object inside a list like below:

[2, 7, 6, 1, 4, 8, 9] 53661168
None
[<__main__.Node object at 0x03597F10>] 53661168

How do I display this Node object correctly? Thanks.

Answer 1

You are trying to reverse the linked list in place.

In your code l was originally the node with value 2. You reversed the list successfully.

But after you call l.reverse(), l still refers to the node with value 2.

You can't make l refer to something else from it's own method.

Is it safe to replace a self object by another object of the same type in a method?

In fact even doing something like:

    def reverse(self):
        prev = None
        current = self

        while current:
            next=current.next
            current.next=prev
            prev=current
            current=next
            
        self.val = prev.val
        self.next = prev.next
        #print(prev)
        return prev

Won't work because now you have created a cycle in your list 7->9 since 7 was originally pointing to self self.__dict__.update(prev.__dict__) won't work for the same reason.

Simply assigning self = prev will also not work since self is just local.

So your best bet is to simply assign l to l.reverse()

l = l.reverse() so that l now actually is the first node of the reversed list.