While reversing a custom linked list recursively, head.next_node suddenly changes to None

Question

I am trying to implement reverse linked list using recursion:

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

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

    def push(self, data):
        new_node=node(data)
        cur_node=self.head
        while(cur_node.next_node!=None):
            cur_node=cur_node.next_node
        cur_node.next_node=new_node



    def display(self):
        elems=[]
        cur_node=self.head
        print('Display:')
        # print(cur_node)
        # print(cur_node.next_node)
        # print(cur_node.data)
        while(cur_node.next_node!=None):
            cur_node=cur_node.next_node
            elems.append(cur_node.data)
        print(elems)


    def lenth(self):
        i=0
        cur_node=self.head
        while(cur_node.next_node!=None):
            last_node=cur_node
            cur_node=cur_node.next_node
            i+=1
        print(i)


    def reversell_rec(self, node):
        # print("Recursive")
        cur_node = node
        # print(cur_node)
        # print(cur_node.next_node)
        # print(cur_node.data)
        if (cur_node.next_node == None):
            self.head.next_node = cur_node
            return
        self.reversell_rec(cur_node.next_node)
        temp=cur_node.next_node
        temp.next_node = node
        node.next_node = None



ll=linked_list()
ll.push(1)
ll.push(2)
ll.display()
ll.reversell_rec(ll.head)
ll.display()

I get the output:

Display:  #Display before recursion
 [1, 2]
Display:  #Display after recursion
 []

I tried different ways of printing them out using objects but somehow it self.head.next_node changes back to "None" even though I am assigning the last node to self.head.next_node to the last node. What is causing the change? Can you please help?

Edit:

def reversell_rec(self, node):
    # print("Recursive")
    cur_node = node
    # print(cur_node)
    # print(cur_node.next_node)
    # print(cur_node.data)
    if (cur_node.next_node == None):
        self.head.next_node = cur_node
        return
    self.reversell_rec(cur_node.next_node)
    if(cur_node!=self.head):
        temp = cur_node.next_node
        temp.next_node = cur_node
        cur_node.next_node = None '

You do realize that your `head`'s data is gonna be `None`, right? — Aakash Verma, Nov 06 '17 at 19:43
Possible duplicate of https://stackoverflow.com/questions/29242000/how-can-i-write-a-recursive-function-to-reverse-a-linked-list — ivan_pozdeev, Nov 06 '17 at 20:54
@ivan_pozdeev: note that the question isn't how to write the assignment; OP wants to know what is wrong with *this* implementation. Your link should be a great help, but I don't know that it qualifies as a duplicate. — Prune, Nov 06 '17 at 21:00
@Prune The question is not formulated in a reusable way and thus is close-worth in my book -- there's simply no need to keep it around, it adds nothing to the site. Maybe if I can change the focus a little though, to highlight the (potentially recurring) specific implementation problem... Here! — ivan_pozdeev, Nov 06 '17 at 21:06
@Prune now, the title has the keywords of the specific symptom, so someone who made a similar mistake _might actually be able to find it._ — ivan_pozdeev, Nov 06 '17 at 21:12

score 0 · Answer 1 · answered Nov 06 '17 at 19:42

0

This looks mutable reverse. If you mean to do it, the basic idea is to construct a reverse by accumulating backwards.

def reversell_rec(self):
    def rev_node(n, acc):
        if n is None: return acc
        nxt = n.next_node
        n.next_node = acc
        return rev_node(nxt, n)

    self.head = rev_node(self.head, None)

But honestly, it's going to be easier if you do it in a while loop if it's mutable.

answered Nov 06 '17 at 19:42

Jason Hu

6,239
1
20
41

@karnesJ.R he is not because he doesn't know how to do it properly. obviously his code is wrong. – Jason Hu Nov 06 '17 at 19:48
This is swweet! – Aakash Verma Nov 06 '17 at 20:07
@AakashVerma you can accept my answer if it does the job. – Jason Hu Nov 06 '17 at 20:21
1

@HuStmpHrrr Bro, I am not the OP xD – Aakash Verma Nov 06 '17 at 20:22
@AakashVerma great – Jason Hu Nov 06 '17 at 20:22

Aakash Verma · Accepted Answer · 2017-11-06T21:02:30.070

The very base condition of your recursion was skipping one of the elements. You were doing self.head.next_node=cur_node instead of just assigning self.head itself to the last element.

I made a little change to the reversell_rec function:

def reversell_rec(self, node):
    # print("Recursive")
    cur_node = node
    # print(cur_node)
    # print(cur_node.next_node)
    # print(cur_node.data)
    if (cur_node.next_node == None):
        self.head = cur_node
        return
    self.reversell_rec(cur_node.next_node)
    temp=cur_node.next_node
    temp.next_node = cur_node
    cur_node.next_node = None

As you have used a "None" head, I had to change the display function as well:

def display(self):
    elems=[]
    cur_node=self.head
    print('Display:')
    # print(cur_node)
    # print(cur_node.next_node)
    # print(cur_node.data)
    if self.head.data!=None:
        while(cur_node.next_node!=None):
            elems.append(cur_node.data)
            cur_node=cur_node.next_node
    else:
        cur_node=cur_node.next_node
        while(cur_node!=None):
            elems.append(cur_node.data)
            cur_node=cur_node.next_node
    print(elems)

Thank you for your reply. I was trying NOT to display the header as it is just a pointer to the data and was trying to only display the data. I have updated the code in the original post: — RajData, Nov 06 '17 at 20:50

While reversing a custom linked list recursively, head.next_node suddenly changes to None

2 Answers2