How can I write a recursive function to reverse a linked list?

Question

I am looking to do it with Python. And I don't want to just print it in reverse, but actually reverse the given nodes. I have seen it done in other languages but had trouble finding an example in Python.

I'm trying to do it in one function, but if a helper function was needed then so be it.

Answer 1

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

Using such a simple linked list implementation:

class LinkedList:
    def __init__ (self, value, next = None):
        self.value = value
        self.next = next
    def __repr__ (self):
        return 'LinkedList({}, {})'.format(self.value, repr(self.next))

Example:

>>> a = LinkedList(1, LinkedList(2, LinkedList(3, LinkedList(4))))
>>> a
LinkedList(1, LinkedList(2, LinkedList(3, LinkedList(4, None))))
>>> b = reverse(a)
>>> b
LinkedList(4, LinkedList(3, LinkedList(2, LinkedList(1, None))))
>>> a # note that there is a new head pointer now
LinkedList(1, None)

Answer 2

I have created a simple implementation of linked list with a reverse method that uses recursion.

class Node(object):
    def __init__(self,initdata):
        self.data = initdata
        self.next = None

class LinkedList(object):
    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head == None

    def add(self,data): #this method adds node at head
        temp = Node(data)
        temp.setNext(self.head)
        self.head = temp

    def traverse(self):
        current = self.head
        while current:
            if current.getNext():
                print(current.data,end="->")
            else:
                print(current.data)
            current = current.getNext()

    def reverse(self,item):
        if item.next == None:
            self.head = item
            return
        self.reverse(item.next)
        temp = item.next
        temp.next = item
        item.next = None


def main():
    mylist = LinkedList()
    mylist.add(15)
    mylist.add(20)
    mylist.add(25)
    mylist.add(30)
    mylist.traverse()
    mylist.reverse(mylist.head)
    mylist.traverse()
    print(mylist.head.data)

if __name__ == "__main__":
    main()

Output:

Before:
30->25->20->15
After:
15->20->25->30

Answer 3

Another way to do it with recursion:

def reverse(head):
  # Empty list is always None
  if not head:
    return None

  # List of length 1 is already reversed
  if not head.get_next():
    return head


  next = head.get_next()

  head.set_next(None)

  rest = reverse(next)

  next.set_next(head)

  return rest

Answer 4

After seeking to thoroughly understand how to reverse a linked list in python using both iterative and recursive methods, and working on an adequate refactoring, I coded this. Many links that I studied seemed slightly unclear or had unnecessary steps. If I have not arrived at the bare minimum / clear steps, I think these are at least close. I felt it best to not include the output, but it will run as is and produce output (python 2.7 and easy to modify for 3.x).

class Node:
def __init__(self,val):
    self.val = val
    self.next = None # the pointer initially points to nothing

def traverse(self):
    # start from the head node
    node = self 
    while node != None:
        # access the node value
        out_string = 'val = %d, loc = %s, next = %s'
        print out_string % (node.val, node, node.next)
        # move on to the next node
        node = node.next 

def reverse_iteratively(self):
    previous = None
    current = None
    head = self

    while head:
        # before reverse
        previous = current
        current = head
        head = head.next
        # reverse the link
        current.next = previous

def reverse_recursively(self, node, pre=None):
    if node.next != None:
        self.reverse_recursively(node.next, pre=node)
    node.next = pre

### Operation Section
node0 = Node(0)
node1 = Node(7);  node0.next = node1
node2 = Node(14); node1.next = node2
node3 = Node(21); node2.next = node3
node4 = Node(28); node3.next = node4
node5 = Node(35); node4.next = node5
node6 = Node(42); node5.next = node6
node7 = Node(49); node6.next = node7
node8 = Node(56); node7.next = node8
node9 = Node(63); node8.next = node9

print "Forward linked:"
node0.traverse()
node0.reverse_recursively(node0)
print "Reverse linked:"
node9.traverse()