Singly linked list is not reversing when using recursion

Question

I'm having trouble figuring out what's missing. I've taken a several looks at other solutions online, and those don't seem to work when I apply the differences. I've spent a good amount of time trying to debug. Here's my code:

def recurse_reverse(self, curr, level):
    print('-' * level, 'curr:', curr.value, '| next:', curr.next.value if curr.next else curr.next)
    if (not curr) or (not curr.next): # if there's 0 or 1 node
        return curr

    # p = self.recurse_reverse(curr.next, level + 1)
    self.recurse_reverse(curr.next, level + 1)

    print('-' * level, 'curr:', curr.value, '->', curr.next.value, '->',
          curr.next.next.value if curr.next.next else curr.next.next)

    curr.next.next = curr
    # checking if pointer moved
    print('-' * level, 'curr:', curr.value, '->', curr.next.value, '->',
          curr.next.next.value if curr.next.next else curr.next.next)
    # curr.next = None
    # return p

The output I get when I call

my_list = SinglyLinkedList()
my_list.add_to_tail(1)
my_list.add_to_tail(2)
my_list.add_to_tail(3)
my_list.add_to_tail(4)

print(my_list._head.value) # 1
print(my_list._head.next.value) # 2 
print(my_list._head.next.next.value) # 3
print(my_list._head.next.next.next.value) # 4

my_list.recurse_reverse(my_list._head, 1)

is this:

- curr: 1 | next: 2
-- curr: 2 | next: 3
--- curr: 3 | next: 4
---- curr: 4 | next: None
--- curr: 3 -> 4 -> None
--- curr: 3 -> 4 -> 3
-- curr: 2 -> 3 -> 4
-- curr: 2 -> 3 -> 2
- curr: 1 -> 2 -> 3
- curr: 1 -> 2 -> 1

So printing at each level, it seems that the pointers are being moved correctly. However when I try to print the linked list's head and tail I call recurse_reverse, I get 1 and 3, respectively; yet, what I would expect is 4 and 1.

In many solutions I've seen, the last line of the code is curr.next = None, to remove the next pointer of the current node, but when include that in my code, I get AttributeError: 'NoneType' object has no attribute 'value'

I've also tried setting

p = self.recurse_reverse(curr.next, level + 1)

and then return p on the last line, but that doesn't work either.

Here's my implementation:

class _LinkNode:
    def __init__(self, value):
        self.value = value
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self._head = None
        self._tail = None
        self._length = 0

    def add_to_tail(self, value):
        """
        Add a new node to the tail of the linked list.

        Parameters
        ----------
        value : int, float, string, dict, list, etc.

        """
        new_node = _LinkNode(value)

        if self._head is None:  # if linked list is empty
            self._head = new_node

        if self._tail:  # if linked list has a tail, i.e. > 1 node
            self._tail.next = new_node

        self._tail = new_node  # regardless of current length, update tail

        self._length += 1

def recurse_reverse(self, curr, level):
    # see above

Please explain what you intend your function to do, and how your linked list implementation works. You provided output with no explanation of the input. — BrenBarn
– BrenBarn, Commented Aug 5, 2016 at 19:34

niemmi · Accepted Answer · 2016-08-05 20:09:41Z

1

There are two issues with your code. First if list contains more than one element you don't swap _head.next, after recurse_reverse it will still point to second element of the original list and thus the last two elements of reversed list form a loop.The second issue is what you don't swap _head and _tail anywhere in your code.

Here's one way to to implement the reversal recursively:

@staticmethod
def reverse(prev, node):
    # Recurse until end of the list
    if node:
        SinglyLinkedList.reverse(node, node.next)
        node.next = prev

def recurse_reverse(self):
    # Reverse nodes
    SinglyLinkedList.reverse(None, self._head)

    # Swap head & tail since they are reversed now
    self._head, self._tail = self._tail, self._head

answered Aug 5, 2016 at 20:09

niemmi

17.3k7 gold badges38 silver badges42 bronze badges

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

Collectives™ on Stack Overflow

Singly linked list is not reversing when using recursion

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