Reversing a LinkedList in python

Question

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.

You'll need a third variable to keep track of the "next" node. curr.next is not a sufficient reference to this node since you're redefining the node's next pointer in the first line of the while loop. — bazzells, Dec 30 '17 at 08:02

coredump · Accepted Answer · 2017-12-30T08:48:06.150

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.

After I make a change, I get `[3, 2, 1, None]` instead of `[4, 3, 2,1 ]` and I am not sure why the 4 is gone. Any idea? — Dawn17, Dec 30 '17 at 08:26

score 0 · Answer 2 · answered Dec 30 '17 at 08:27

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).

After I make a change, I get [3, 2, 1, None] instead of [4, 3, 2,1 ] and I am not sure why the 4 is gone. Any idea? — Dawn17, Dec 30 '17 at 08:30

Reversing a LinkedList in python

2 Answers2

Reverse

Display