Question

PYTHON : Describe a fast recursive algorithm for reversing a singly linked list

Answer 1

ANSWER:

Python program to reverse singly linked list using recursion

Algorithm :

step 1 : start

Step 2 : Create class Node

Step 3: Create constructor to initialize the node object

Step 4: Create class LinkedList

Step 5 : Define function to initialize head

Step 6: Call function reverse(a) to reverse linked list

Step 7 : Assign prev node none and current value of head

Step 8 : Define function push(a,node) to insert new node at the beginning

Step 9:   create Utility function to print the linked LinkedList

Step 10: Define Driver program to test all functions

Step 11: Stop

Program Code

class Node:
    def __init__(a, data):
        a.data = data
        a.next = None
 class LinkedList:
    def __init__(a):
        a.head = None
 
    def reverse(a, head):
 
       
        if head is None or head.next is None:
            return head      
        rest = a.reverse(head.next)   
        head.next.next = head
        head.next = None
        return rest
 
    
    def __str__(a):
        linkedListStr = ""
        temp = a.head
        while temp:
           linkedListStr = (linkedListStr + str(temp.data) + " ")
            temp = temp.next
        return linkedListStr
 
    def push(a, data):
        temp = Node(data)
        temp.next = a.head
        a.head = temp
 

linkedList = LinkedList()
linkedList.push(20)
linkedList.push(4)
linkedList.push(15)
linkedList.push(85)
 
print("Given linked list")
print(linkedList)
 
linkedList.head = linkedList.reverse(linkedList.head)
 
print("Reversed linked list")
print(linkedList)