CODEWITHSUNDEEP
pythonlinked-list
Dawn17
Dawn17

Reputation: 8297

Reversing a LinkedList in python

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

class linked_list:
    def __init__(self):
        self.head = node()

This is how I initialize my LinkedList data structure in python.

After I append some nodes, by doing

my_list.append(1)
my_list.append(2)
my_list.append(3)
my_list.append(4)

and display it using the function that I wrote,

def display(self):

    elems = []
    curr = self.head

    while curr.next != None:
        curr = curr.next
        elems.append(curr.data)

    print(elems)

It prints out [1, 2, 3, 4] which seems fine.

However, when I try to reverse it by using the function below

def reverseList(self):

    curr = self.head
    prev = None


    while curr != None:

        curr.next = prev
        prev = curr
        curr = curr.next

    self.head = prev

It gives me an empty linkedList []. If I draw the LinkedList on a paper, it seems fine and I don't see what I am doing wrong.

Upvotes: 2

Views: 933

Answers (2)

coredump
coredump

Reputation: 38799

Reverse

Look at the order of your operations:

curr.next = prev
prev = curr
curr = curr.next

Before you do curr = curr.next, curr.next is equal to prev, which is equal to None (during the first, and final iteration).

You need to store the value of curr.next in an intermediate variable before changing it.

Alternatively, you can use Python's multiple assignment (Multiple assignment and evaluation order in Python) to assign all variables at once after evaluating their values:

curr.next, prev, curr = prev, curr, curr.next

Display

You have the same kind of problem in the display function.

while curr.next != None:
    curr = curr.next
    elems.append(curr.data)

You don't append the first curr.data, you directly change curr into curr.next.

Upvotes: 2

Laurent LAPORTE
Laurent LAPORTE

Reputation: 22952

As mentioned by @bazzells, you need a third variable to keep track of the next node before discarding it:

def reverse(self):
    curr = self.head
    prev = None
    while curr is not None:
        next_ = curr.next
        curr.next = prev
        prev = curr
        curr = next_
    self.head = prev

Note on code style:

  • use is None or is not None to compare an instance with Nome because you only need to compare identity (memory address).
  • class names should be in CamelCase,
  • variable and function names should be in snake_case.
  • avoid using next in your code because it’s a built-in function and can also be confusing (replace by next_node, for instance).

Upvotes: 0

Related Questions