How can I reverse my singly linked list of nodes in Python?

Question

Code snippets are below: trying to reverse my list of nodes but when I do so, only one node (the first in the linked list) prints. Any idea what I'm doing wrong here? I've written this out on paper and it seems like it should loop through my nodes, adding each one into my new linked list?

# node class
class Node(object):
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

# singly linked list class
class SinglyLinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None

# I'm trying to do the same thing in my reverseList() method
# as I'm doing in the addFront method
def addFront(self, value):
    # create new node
    newNode = Node(value)
    # set old head to point to new node
    if self.head == None:
        self.head = newNode
        self.tail = newNode
    else:
        # store old head
        last_head = self.head
        # set head to new node
        self.head = newNode
        # point head to old head
        self.head.next = last_head

# reverseList() method not working? 
# Only giving me first head value? Why?
def reverseList(self):
        node = self.head
        newList = SinglyLinkedList()
        newList.head = None
        while node:
            if node.next == None:
                break
            else:
                temp = newList.head
                newList.head = node
                newList.head.next = temp
                print newList.head.value
                node = node.next

Jonas · Accepted Answer · 2016-09-22 07:07:06Z

1

It seems that your code is skipping the last element of the list due to you setting node == node.next and then asks if node.next has a value. Your new list also reuses the nodes of the existing list which cause them to share the object. This is not likely to be the desired behaviour as any changes to nodes of one list would result in changes to the other list. Especially if you add new elements to one of them you would start experiencing that your list is behaving strange.

The following code creates a new list which contains the values of the original list in reverse order.

def revers(self):
    rev = SinglyLinkedList()
    node = self.head

    while node:
        newNode = Node(node.value)
        if not rev.tail:
            rev.tail = newNode
        newNode.next = rev.head
        rev.head = newNode
        node = node.next

    return rev

The following code revers a list.

def revers(self):
    prev = self.head
    next = self.head.next
    prev.next = None

    while next:
        temp = next.next
        next.next = prev
        prev = next
        next = temp

    self.head, self.tail = self.tail, self.head

A comment about your code. It's is generally a bad idea to mix functional and imperative like behaviour. Your addFront function modifies the list object, while the reverse function you asks for create a new list. All your functions should either create a new list, or modify the current instance. Mixing it like this makes it very hard to predict the behaviour of your list.

edited Sep 22, 2016 at 7:07

answered Sep 22, 2016 at 6:50

Jonas

7971 gold badge8 silver badges21 bronze badges

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

1 Comment

twk Over a year ago

I couldn't ask for more robust feedback, thank you greatly for all you've outlined and I understand now what you're saying about functional/imperative behavior -- I was butting my head against the wall trying to find this solution, this my walk into imperative behavior land, but what you've accomplished (reversing the existing list) is stellar and the exact solution I was seeking. Answer accepted and your feedback and contributions are greatly valued!

Gerrat · Accepted Answer · 2016-09-22 03:06:56Z

0

Part of the issue occurs with the newList.head = node assignment, followed by: newList.head.next = temp. The first line makes both of these references point to the same thing, and the next line will now change both (since they now can be used interchangeably).

I think you need to assign the previous head to the tail of your new list as you go:

def reverseList(self):
    node = self.head
    newList = SinglyLinkedList()
    newList.head = None
    while node:
        if node.next == None:
            break
        else:
            temp = newList.head
            newList.head = node
            newList.tail = temp
            print newList.head.value
            node = node.next

Edit: If you don't mind creating new node (objects) that just contain the value of the old node objects (which is what I think addFront is doing), you should be able to simply replace:

newList.head = node

with

newList.head = Node(node.value, node.next)

in your original post.

edited Sep 22, 2016 at 3:06

answered Sep 22, 2016 at 1:50

Gerrat

29.9k9 gold badges78 silver badges104 bronze badges

3 Comments

twk Over a year ago

I appreciate this feedback: to explain, I was attempting to simulate a working method that I built, "addFront()", which adds values to the front of a linked list. My goal with reverseList() was to (1) create a new list (2) set the head of the new list to be the head of the old list (3) add the next item in the old list to the new list while replacing the current head with the new item, and then linking the new item to the old head (as its next property). I'll add my addFront() method to my code above -- does it make more sense what I'm trying to accomplish / my logic?

Gerrat Over a year ago

@natureminded: I think I understand (but not positive) - I edited my answer

twk Over a year ago

I really appreciate all of your hard work to help me out here, I did try your solution with the updated Node code, but my list still seems to be in the same order. I have a feeling it's close but I think Jonas has a little cleaner method than what I was attempting. I really appreciate you trying to help me make sense of my code though :)

Basant Rules · Accepted Answer · 2016-09-22 03:58:10Z

0

We can reverse the list by recursive function

def reverse (item, tail = None):
    next = item.next
    item.next = tail
    if next is None:
        return item
    else:
        return reverse(next, item)

For reference visit: http://www.geeksforgeeks.org/reverse-a-list-in-groups-of-given-size/

answered Sep 22, 2016 at 3:58

Basant Rules

81712 silver badges9 bronze badges

1 Comment

twk Over a year ago

I did try your solution and appreciate your feedback! When I run the code snippet above I get the following attribute error: AttributeError: 'SinglyLinkedList' object has no attribute 'next' -- any idea? Thank you greatly!

Collectives™ on Stack Overflow

How can I reverse my singly linked list of nodes in Python?

3 Answers 3

1 Comment

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related