Reverse a linked list by Tail Recursive Method

The idea is to maintain three pointers previous, current and next, recursively visit every node and make links using these three pointers.

Follow the steps below to solve the problem:

First update next with next node of current i.e. next = current->next
Now make a reverse link from current node to previous node i.e. curr->next = prev
If the visited node is the last node then just make a reverse link from the current node to previous node and update head.

Below is the implementation of the above approach:

C++

// A simple and tail recursive C++ program to reverse
// a linked list
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* next;
      Node(int x) {
        data = x;
          next = NULL;
    }
};

void reverseUtil(Node* curr, Node* prev, Node** head);

// This function mainly calls reverseUtil()
// with prev as NULL
void reverse(Node** head)
{
    if (!head)
        return;
    reverseUtil(*head, NULL, head);
}

// A simple and tail-recursive function to reverse
// a linked list.  prev is passed as NULL initially.
void reverseUtil(Node* curr, Node* prev, Node** head)
{
    /* If last node mark it head*/
    if (!curr->next) {
        *head = curr;
        /* Update next to prev node */
        curr->next = prev;
        return;
    }
    /* Save curr->next node for recursive call */
    Node* next = curr->next;
    /* and update next ..*/
    curr->next = prev;
    reverseUtil(next, curr, head);
}

// A utility function to print a linked list
void printlist(Node* head)
{
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

// Driver code
int main()
{
    Node* head1 = new Node(1);
    head1->next = new Node(2);
    head1->next->next = new Node(3);
    head1->next->next->next = new Node(4);
    head1->next->next->next->next = new Node(5);
    head1->next->next->next->next->next = new Node(6);
    head1->next->next->next->next->next->next = new Node(7);
    head1->next->next->next->next->next->next->next
        = new Node(8);
    cout << "Given linked list\n";
    printlist(head1);
    reverse(&head1);
    cout << "Reversed linked list\n";
    printlist(head1);
    return 0;
}

// A simple and tail recursive C program to reverse a linked
// list
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

void reverseUtil(Node* curr, Node* prev, Node** head);

// This function mainly calls reverseUtil()
// with prev as NULL
void reverse(Node** head)
{
    if (!head)
        return;
    reverseUtil(*head, NULL, head);
}

// A simple and tail-recursive function to reverse
// a linked list.  prev is passed as NULL initially.
void reverseUtil(Node* curr, Node* prev, Node** head)
{
    /* If last node mark it head*/
    if (!curr->next) {
        *head = curr;
        /* Update next to prev node */
        curr->next = prev;
        return;
    }

    /* Save curr->next node for recursive call */
    Node* next = curr->next;
    /* and update next ..*/
    curr->next = prev;
    reverseUtil(next, curr, head);
}

// A utility function to create a new node
Node* newNode(int key)
{
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = key;
    temp->next = NULL;
    return temp;
}

// A utility function to print a linked list
void printlist(Node* head)
{
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// Driver code
int main()
{
    Node* head1 = newNode(1);
    head1->next = newNode(2);
    head1->next->next = newNode(3);
    head1->next->next->next = newNode(4);
    head1->next->next->next->next = newNode(5);
    head1->next->next->next->next->next = newNode(6);
    head1->next->next->next->next->next->next = newNode(7);
    head1->next->next->next->next->next->next->next
        = newNode(8);
    printf("Given linked list\n");
    printlist(head1);
    reverse(&head1);
    printf("Reversed linked list\n");
    printlist(head1);
    return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java program for reversing the Linked list

class LinkedList {

    static Node head;
    static class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
    // A simple and tail recursive function to reverse
    // a linked list.  prev is passed as NULL initially.
    Node reverseUtil(Node curr, Node prev)
    {
        /*If head is initially null OR list is empty*/
        if (head == null)
            return head;
        /* If last node mark it head*/
        if (curr.next == null) {
            head = curr;
            /* Update next to prev node */
            curr.next = prev;
            return head;
        }
        /* Save curr->next node for recursive call */
        Node next1 = curr.next;
        /* and update next ..*/
        curr.next = prev;
        reverseUtil(next1, curr);
        return head;
    }

    // prints content of double linked list
    void printList(Node node)
    {
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }

    // Driver Code
    public static void main(String[] args)
    {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        list.head.next = new Node(2);
        list.head.next.next = new Node(3);
        list.head.next.next.next = new Node(4);
        list.head.next.next.next.next = new Node(5);
        list.head.next.next.next.next.next = new Node(6);
        list.head.next.next.next.next.next.next
            = new Node(7);
        list.head.next.next.next.next.next.next.next
            = new Node(8);

        System.out.println("Given linked list ");
        list.printList(head);
        Node res = list.reverseUtil(head, null);
        System.out.println("\nReversed linked list ");
        list.printList(res);
    }
}

// This code is contributed by Aditya Kumar (adityakumar129)

Python

# Simple and tail recursive Python program to
# reverse a linked list

# Node class


class Node:

    # Constructor to initialize the node object
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:

    # Function to initialize head
    def __init__(self):
        self.head = None

    def reverseUtil(self, curr, prev):

        # If last node mark it head
        if curr.next is None:
            self.head = curr

            # Update next to prev node
            curr.next = prev
            return

        # Save curr.next node for recursive call
        next = curr.next

        # And update next
        curr.next = prev

        self.reverseUtil(next, curr)

    # This function mainly calls reverseUtil()
    # with previous as None

    def reverse(self):
        if self.head is None:
            return
        self.reverseUtil(self.head, None)

    # Function to insert a new node at the beginning

    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    # Utility function to print the linked LinkedList
    def printList(self):
        temp = self.head
        while(temp):
            print (temp.data, end=" ")
            temp = temp.next


# Driver code
llist = LinkedList()
llist.push(8)
llist.push(7)
llist.push(6)
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)

print ("Given linked list")
llist.printList()

llist.reverse()

print ("\nReversed linked list")
llist.printList()

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

// C# program for reversing the Linked list
using System;

public class LinkedList {
    Node head;
    public class Node {

        public int data;
        public Node next;

        public Node(int d)
        {
            data = d;
            next = null;
        }
    }

    // A simple and tail-recursive function to reverse
    // a linked list. prev is passed as NULL initially.
    Node reverseUtil(Node curr, Node prev)
    {

        /* If last node mark it head*/
        if (curr.next == null) {
            head = curr;

            /* Update next to prev node */
            curr.next = prev;

            return head;
        }

        /* Save curr->next node for recursive call */
        Node next1 = curr.next;

        /* and update next ..*/
        curr.next = prev;

        reverseUtil(next1, curr);
        return head;
    }

    // prints content of double linked list
    void printList(Node node)
    {
        while (node != null) {
            Console.Write(node.data + " ");
            node = node.next;
        }
    }

    // Driver code
    public static void Main(String[] args)
    {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        list.head.next = new Node(2);
        list.head.next.next = new Node(3);
        list.head.next.next.next = new Node(4);
        list.head.next.next.next.next = new Node(5);
        list.head.next.next.next.next.next = new Node(6);
        list.head.next.next.next.next.next.next
            = new Node(7);
        list.head.next.next.next.next.next.next.next
            = new Node(8);

        Console.WriteLine("Given linked list ");
        list.printList(list.head);
        Node res = list.reverseUtil(list.head, null);
        Console.WriteLine("\nReversed linked list ");
        list.printList(res);
    }
}

// This code contributed by Rajput-Ji

Javascript

<script>
// javascript program for reversing the Linked list

    var head;
 class Node {
        constructor(d) {
            this.data = d;
            this.next = null;
        }
    }

    // A simple and tail recursive function to reverse
    // a linked list. prev is passed as NULL initially.
    function reverseUtil(curr,  prev) 
    {
    
        /* If head is initially null OR list is empty */
        if (head == null)
            return head;
            
        /* If last node mark it head */
        if (curr.next == null) {
            head = curr;

            /* Update next to prev node */
            curr.next = prev;
            return head;
        }

        /* Save curr->next node for recursive call */
        var next1 = curr.next;

        /* and update next .. */
        curr.next = prev;

        reverseUtil(next1, curr);
        return head;
    }

    // prints content of var linked list
    function printList(node) {
        while (node != null) {
            document.write(node.data + " ");
            node = node.next;
        }
    }

    // Driver Code
        var head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(6);
        head.next.next.next.next.next.next = new Node(7);
        head.next.next.next.next.next.next.next = new Node(8);

        document.write("Original Linked list<br/> ");
        printList(head);
        var res = reverseUtil(head, null);
        document.write("<br/>");
        document.write("Reversed linked list <br/>");
        printList(res);

// This code is contributed by Rajput-Ji 
</script>

Output

Given linked list
1 2 3 4 5 6 7 8 
Reversed linked list
8 7 6 5 4 3 2 1

Time Complexity: O(N), Visiting every node of the linked list of size N.
Auxiliary Space: O(N), Function call stack space

Reverse a Linked List

Given a pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.

Examples:

Input: Head of following linked list
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULL

Input: Head of following linked list
1->2->3->4->5->NULL
Output: Linked list should be changed to,
5->4->3->2->1->NULL

Input: NULL
Output: NULL

Input: 1->NULL
Output: 1->NULL

Reverse a linked list by Tail Recursive Method

Reverse a Linked List

Categories

Contact US

Reverse a linked list by Tail Recursive Method

Reverse a Linked List

Similar Reads

Categories

Contact US