single linked list reverse in python

Question

i'm trying to create a simple single linked list in python. (i know there is no need to implement list in python, but that's not the point)

here is my code:

class Node:
    def __init__(self,data):
        self.data = data
        self.next= None



class List:
    def __init__(self):
        self.firstNode = Node(None)

    def inserthead(self,newnode):
        if not self.firstNode.next:
            newnode.next = None
            self.firstNode.next = newnode
        else:
            newnode.next = self.firstNode.next
            self.firstNode.next= newnode


    def __show(self,start):
        if start.next:
            print start.data
            self.__show(start.next)

    def printlist(self):
        self.__show(self.firstNode)

    def __reverte_recursive(self,node):
        temp = None
        if not node.next: return node
        else:
            temp = self.__reverte_recursive(node.next)
            node.next.next= node
            node.next = None
        return temp

    def reverte_list1(self):
        self.firstNode=self.__reverte_recursive(self.firstNode)

    def __reverte_iterative(self,node):
        temp = None
        previous = None
        while node and node.next:
            temp = node.next
            node.next= previous
            previous = node
            node = temp
        return previous
    def reverte_iterative(self):
        self.firstNode=self.__reverte_iterative(self.firstNode)

nodeA = Node("A")
nodeB = Node("B")
nodeC = Node("C")
nodeD = Node("D")
nodeE = Node("E")


list1= List()

list1.inserthead(nodeA)
list1.inserthead(nodeB)
                           class Node:
    def __init__(self,data):
        self.data = data
        self.next= None



class List:
    def __init__(self):
        self.firstNode = Node(None)

    def inserthead(self,newnode):
        if not self.firstNode.next:
            newnode.next = None
            self.firstNode.next = newnode
        else:
            newnode.next = self.firstNode.next
            self.firstNode.next= newnode


    def __show(self,start):
        if start.next:
            print start.data
            self.__show(start.next)

    def printlist(self):
        self.__show(self.firstNode)

    def __reverte_recursive(self,node):
        temp = None
        if not node.next: return node
        else:
            temp = self.__reverte_recursive(node.next)
            node.next.next= node
            node.next = None
        return temp

    def reverte_list1(self):
        self.firstNode=self.__reverte_recursive(self.firstNode)

    def __reverte_iterative(self,node):
        temp = None
        previous = None
        while node and node.next:
            temp = node.next
            node.next= previous
            previous = node
            node = temp
        return previous
    def reverte_iterative(self):
        self.firstNode=self.__reverte_iterative(self.firstNode)

nodeA = Node("A")
nodeB = Node("B")
nodeC = Node("C")
nodeD = Node("D")
nodeE = Node("E")


list1= List()

list1.inserthead(nodeA)
list1.inserthead(nodeB)
list1.inserthead(nodeC)
list1.inserthead(nodeD)
list1.inserthead(nodeE)


print "list"
list1.printlist()
print "list reverse"
list1.reverte_list1()
list1.printlist()
list1.reverte_iterative()
print "list reverse reverse"
list1.printlist()

and there are the result:

None
E
D
C
B
list reverse
A
B
C
D
E
list reverse reverse
E
D
C
B

for some reason i can't print all the list and in the first case doesn't print the "A" Node but print the first node(but i checkd and the B node points to A) the first reverse is OK but the third again don't print the A node even if it's pointed by the B Node. probably the problem of the printing is in the __show function. but i suppose i a conceptual bug.

thanks

C is easyer better for this kind of things, but i'm training for an interview and i wanted to see how this was possible in python — kurojishi
– kurojishi, Commented Dec 18, 2011 at 23:37

yurib · Accepted Answer · 2011-12-18 23:40:29Z

3

def __show(self,start):
   if start.next:
       print start.data
       self.__show(start.next)

that only prints the current node if it has a next node, thats why the last node is never printed. should be:

def __show(self,start):
   if start:
       print start.data
       self.__show(start.next)

you make similar mistakes of checking/assigning a node instead of it's next and vice versa throughout the code (in inserthead() for example - which is causing the None being printed)

edited Dec 18, 2011 at 23:40

answered Dec 18, 2011 at 23:35

yurib

8,1573 gold badges32 silver badges55 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

single linked list reverse in python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related