Aditya Trivedi

Data Structures and Algorithms

Reverse a Linked List

Problem Statement

The objective is to reverse a given linked list, which involves altering the pointers between nodes such that the last node becomes the new head node, and each subsequent node points to its predecessor.

For Example:

Input1 :

2->3->4->5->NULL

Output1 :

5->4->3->2->NULL

Input2 :

5->NULL

Output2 :

5->NULL

Input3 :

NULL

Output3 :

NULL

Approach 1 : Iterative Method

First, that is the iterative approach to reverse a linked list is given below.

Algorithm

  1. Initialize three-pointers that are curr, prev, and next with NULL values.
  2. Go through the linked list iteratively.
    Perform the following in a loop :
// Store the next node before changing the current’s next.
next = curr->next
// Now change the next of the current. That’s where the real reversing takes place.
curr->next = prev
// Advance prev and curr by one step.
prev = curr
curr = next

Code Implementation

  • In C++
// Iterative program
#include <iostream>
using namespace std;

/* Linked list node structure*/
struct node {
    int val;
    struct node* next;
    Node(int val){
        this->val = val;
        next = NULL;
    }
};

struct Linked_List {
    node* head;
    Linked_List() { head = NULL; }

    /* Function for reversing linked list */
    void reverse_ll(){
        // Set the pointers for the current, previous, and next values.
        node* curr = head;
        node *prev = NULL, *next = NULL;

        while (curr != NULL) {
            // Storing next
            next = curr->next;
            // Reversing current node pointer
            curr->next = prev;
            // Move all 3 pointers to one position ahead.
            prev = curr;
            curr = next;
        }
        head = prev;
    }

    /* Function for printing linked list */
    void print_ll(){
        struct node* temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }

    void push(int data){
        node* temp = new node(data);
        temp->next = head;
        head = temp;
    }
};

/* Driver code*/
int main(){
    Linked_List llist;
    llist.push(2);
    llist.push(4);
    llist.push(6);
    llist.push(8);

    cout << "Original Linked List\n";
    llist.print_ll();

    llist.reverse_ll();

    cout << "\nFinal Reversed Linked List \n";
    ll.print();
    return 0;
}
  • In Java
// Java program for reversing the linked list

class Linked_List {
  static Node head;

  static class Node {
    int data;
    Node next;

    Node(int val) {
      data = val;
      next = null;
    }
  }

  /* Function for reversing the linked list */
  Node reverse_linkedlist(Node node) {
    Node prev = null;
    Node curr = node;
    Node next = null;
    while (curr != null) {
      next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }
    node = prev;
    return node;
  }

  // prints the double linked_list
  void print_LinkedList(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(85);
    list.head.next = new Node(15);
    list.head.next.next = new Node(4);
    list.head.next.next.next = new Node(20);

    System.out.println("Given Linked List");
    list.print_LinkedList(head);
    head = list.reverse_linkedlist(head);
    System.out.println("");
    System.out.println("Reversed Linked List ");
    list.print_LinkedList(head);
  }
}
  • In Python
class Node:

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


class Linked_List:

    # Function for initializing the head
    def __init__(self):
        self.head = None

    # Function to reverse the linked list
    def reverse_ll(self):
        prev = None
        curr = self.head
        while(curr is not None):
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        self.head = prev

    # Function for inserting a new node at the beginning of ll
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    # function for printing the Linked_List
    def printLinkedList(self):
        temp = self.head
        while(temp):
            print temp.data,
            temp = temp.next


# Driver code
l_list = Linked_List()
l_list.push(2)
l_list.push(4)
l_list.push(6)
l_list.push(8)

print("Original Linked List")
l_list.printLinkedList()
l_list.reverse_ll()
print("\nFinal Reversed Linked List")
l_list.printLinkedList()

Output :

Original Linked List
2 4 6 8
Final Reversed Linked List
8 6 4 2

Complexity Analysis

Time Complexity :
As we will iterate over the whole linked list of size “n” so the time complexity of this approach will be O(n).

Space Complexity :
As no extra memory is being used in this approach so auxiliary space consumed will be O(1).

Approach 2 : Recursive Method

Second, that is a recursive approach to reverse a linked list is given below.

Algorithm

  1. The first node and the remainder of the linked list should be separated into two parts.
  2. For the remaining linked list items, call reverse.
  3. Link the rest to the first.
  4. Fix the head pointer.

Code Implementation

  • In C++
#include <iostream>
using namespace std;

/* Link list node */
struct Node {
    int data;
    struct Node* next;
    Node(int val){
        this->data = val;
        next = NULL;
    }
};

struct Linked_List {
    Node* head;
    Linked_List(){
        head = NULL;
    }

    Node* reverse_ll(Node* head){
        //checking if linkedlist is empty or there is a single node then return the head of the linkedlist
        if (head == NULL || head->next == NULL)
            return head;

        /* Put the very first element there at the end and flip the rest of the list around. */
        Node* rest = reverse_ll(head->next);
        head->next->next = head;
        head->next = NULL;
        return rest;
    }
     //function to print linked list
    void print_linkedlist(){
        struct Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }
     //function for pushing data inside the node
    void push_data(int val){
        Node* temp = new Node(val);
        temp->next = head;
        head = temp;
    }
};

int main(){
    Linked_List llist;
    llist.push_data(2);
    llist.push_data(4);
    llist.push_data(6);
    llist.push_data(8);

    cout << "Original LinkedList\n";
    llist.print_linkedlist(); //call the print function

    llist.head = llist.reverse_ll(llist.head); //call the reverse list function

    cout << "\nFinal Reversed LinkedList \n";
    ll.print_linkedlist(); //call the print function
    return 0;
}
  • In Java
class recursion {
  static Node head; // head of the list

  static class Node {
    int data;
    Node next;

    Node(int val) {
      data = val;
      next = null;
    }
  }

  static Node reversell(Node head) {
    if (head == null || head.next == null) return head;

    /* Put the very first element there at the end and flip the rest of the list around.*/
    Node rest = reversell(head.next);
    head.next.next = head;
    head.next = null;

    /* fixing head pointer */
    return rest;
  }

  /* Function for printing the linked_list */
  static void printll() {
    Node temp = head;
    while (temp != null) {
      System.out.print(temp.data + " ");
      temp = temp.next;
    }
    System.out.println();
  }

  static void push(int val) {
    Node temp = new Node(val);
    temp.next = head;
    head = temp;
  }

  /* Driver program*/
  public static void main(String args[]) {
    push(2);
    push(4);
    push(6);
    push(8);

    System.out.println("Original Linked List");
    print();

    head = reversell(head);

    System.out.println("Final Reversed Linked List");
    print();
  }
}
  • In Python
class Node:
    def __init__(self, val):
        self.data = val
        self.next = None

class Linked_List:
    def __init__(self):
        self.head = None # Head of the list

    # Function for reversing the linked list
    def reversell(self, head):

        # If the head is empty or the list end has been reached
        if the head is None or head.next is None:
            return head

        # Reversing the rest of the list
        rest = self.reversell(head.next)

        # Put the first element at the end
        head.next.next = head
        head.next = None

        # Fixing header pointer
        return rest

    # Return linked list in display format
    def __str__(self):
        linkedList_Str = ""
        temp = self.head
        while temp:
            linkedList_Str = (linkedList_Str +
                            str(temp.data) + " ")
            temp = temp.next
        return linkedList_Str

    # Pushing the new data at the head of the list
    def push_data(self, val):
        temp = Node(val)
        temp.next = self.head
        self.head = temp

# Driver code
linked_List = Linked_List()
linked_List.push_data(2)
linked_List.push_data(4)
linked_List.push_data(6)
linked_List.push_data(8)

print("Original Linked List")
print(linked_List)

linked_List.head = linked_List.reversell(linked_List.head)

print("Final Reversed Linked List")
print(linked_List)

Output :

Original Linked List
2 4 6 8
Final Reversed Linked list
8 6 4 2

Complexity Analysis

Time Complexity :
As we are iterating over the linked list with “n” nodes to reverse it then time complexity will be O(n).

Space Complexity :
As we are using extra “n” size space for performing this approach thus it will consume O(n) auxiliary space.

Approach 3 : Tail Recursive Method

As in the previous two approaches we have used the iterative and recursive methods now here we will use this tail recursive method to reverse a linked list.

Code Implementation

  • In C++
#include <bits/stdc++.h>
using namespace std;

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

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

// this function calls reverseUtil() with prev set to NULL.

void reverse_ll(Node** head){
    if (!head)
        return;
    reverse_Util(*head, NULL, head);
}

// A straightforward function to reverse a linked list that is tail-recursive. Prev is initially passed as NULL.
void reverse_Util(Node* curr, Node* prev, Node** head){
    if (!curr->next) {
        *head = curr;
        /* Updating next to the prev node */
        curr->next = prev;
        return;
    }
    /* Saving curr->next node for the recursive call */
    Node* next = curr->next;
    /* now update the next ..*/
    curr->next = prev;
    reverse_Util(next, curr, head);
}

// Utility function for creating a new node
Node* newNode(int val){
    Node* temp = new Node;
    temp->data = val;
    temp->next = NULL;
    return temp;
}

// Utility function for printing a linked list
void printlinkedlist(Node* head){
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

// Driver code
int main(){
    Node* head1 = newNode(2);
    head1->next = newNode(4);
    head1->next->next = newNode(6);
    head1->next->next->next = newNode(8);
    cout << "Original Linked List\n";
    printlist(head1);
    reverse(&head1);
    cout << "\nFinal Reversed Linked List\n";
    printlinkedlist(head1);
    return 0;
}
  • In Java
class Linked_List {
  static Node head;

  static class Node {
    int data;
    Node next;

    Node(int val) {
      data = val;
      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 the head is initially null OR the list is empty*/
    if (head == null) return head;
    /* If the last node marks its 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 the double-linked list
  void printLinkedList(Node node) {
    while (node != null) {
      System.out.print(node.data + " ");
      node = node.next;
    }
  }

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

    System.out.println("Original Linked List ");
    list.printLinkedList(head);
    Node res = list.reverseUtil(head, null);
    System.out.println("");
    System.out.println("");
    System.out.println("Final Reversed Linked List ");
    list.printList(res);
  }
}
  • In Python
class Node:

    def __init__(self, val):
        self.data = val
        self.next = None


class Linked_List:

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

    def reverse_Util(self, curr, prev):

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

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

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

        # And update the next
        curr.next = prev

        self.reverse_Util(next, curr)

    # this function calls reverse_Util() with prev set to NULL.
    def reversell(self):
        if self.head is None:
            return
        self.reverse_Util(self.head, None)


    def push_data(self,data):
        node = Node(data)
        node.next = self.head
        self.head = node

    # function to print linked list
    def printllist(self):
        temp = self.head
        while(temp):
            print temp.data,
            temp = temp.next


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

print("Original Linked List")
llist.printllist()

llist.reversell()

print("\nReversed Linked List")
llist.printllist()

Output :

Original Linked List
2 4 6 8
Reversed Linked List
8 6 4 2

Complexity Analysis

Time Complexity :
As we are iterating over the linked list of size “n” for reversing it, so time complexity will be O(n).

Space Complexity :
As no extra space is required in this approach so it will take O(1) auxiliary space.

Approach 4: Using Stack

Algorithm

  1. Store the values in the stack until all the values are entered.
  2. Update a Head pointer to a final location(last node) once all entries have been made.
  3. Until the stack is empty, begin popping up the nodes and storing them in the same order.
  4. Update the last Node’s next pointer in the stack with NULL.

Code Implementation

  • In C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

// Method for reversing a linked list
void reverse_ll(Node** head){
    // Create stack "st"
    stack<Node*> st;
    Node* temp = *head;
    while (temp->next != NULL) {
        st.push(temp);
        temp = temp->next;
    }
    *head = temp;
    while (!st.empty()) {
        // Storing the top value of the stack
        temp->next = st.top();
        // Poping up value from the stack
        st.pop();
        // updating the next pointer in the list
        temp = temp->next;
    }
    temp->next = NULL;
}

// Method for Displaying elements in the List
void printllist(Node* temp){
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

// inserting back the linked list
void insert_backll(Node** head, int val){

    Node* temp = new Node();
    temp->data = val;
    temp->next = NULL;

    if (*head == NULL) {
        *head = temp;
        return;
    }
    else {
        Node* lastnode = *head;
        while (lastnode->next != NULL)
            lastnode = lastnode->next;
        lastnode->next = temp;
        return;
    }
}


int main(){
    Node* head = NULL;
    insert_backll(&head, 2);
    insert_backll(&head, 4);
    insert_backll(&head, 6);
    insert_backll(&head, 8);
    cout << "Original Linked List\n";
    printllist(head);
    reverse_ll(&head);
    cout << "\nFinal Reversed Linked List\n";
    printllist(head);
    return 0;
}
  • In Java
import java.util.*;

class LinkedList {

    static class Node {
        int data;
        Node next;
    };
    static Node head = null;
    // Method for reversing a linked list
    static void reverse_ll(){

        // Creating stack "s"
        Stack<Node> st = new Stack<>();
        Node temp = head;
        while (temp.next != null)
            st.add(temp);
            temp = temp.next;
        }
        head = temp;
        while (!st.isEmpty()) {
            // Storing the top value of the stack in the list
            temp.next = st.peek();
            // Poping up the value from the stack
            st.pop();
            // updating the next pointer in the list
            temp = temp.next;
        }
        temp.next = null;
    }

    // Method for Displaying elements in the List
    static void printllist(Node temp){
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }

    static void insert_backll(int value){

        Node temp = new Node();
        temp.data = value;
        temp.next = null;
        if (head == null) {
            head = temp;
            return;
        }
        else {
            Node lastnode = head;
            while (lastnode.next != null)
                lastnode = lastnode.next;
            lastnode.next = temp;
            return;
        }
    }

    public static void main(String[] args){
        insert_backll(1);
        insert_backll(2);
        insert_backll(3);
        insert_backll(4);
        System.out.print("Original Linked List\n");
        printllist(head);
        reverse_ll();
        System.out.print("\nFinal Reversed Linked List\n");
        printllist(head);
    }
}
  • In Python
class LListNode:
    def __init__(self, data=0, next=None):
        self.val = data
        self.next = next


class Solution:
    def reverse_ll(self, head):

        st, temp = [], head

        while temp:
            st.append(temp)
            temp = temp.next

        head = temp = st.pop()

        while len(st) > 0:
            temp.next = st.pop()
            temp = temp.next

        temp.next = None
        return head


if __name__ == "__main__":
    head = LListNode(2, LListNode(4, LListNode(6,
                        LListNode(8, LListNode(10)))))
    obj = Solution()
    head = obj.reverse_ll(head)
    while head:
        print(head.val, end=' ')
        head = head.next

Output :

Original Linked List
2 4 6 8
Final Reversed Linked List
8 6 4 2

Complexity Analysis

Time Complexity :
As we are iterating over the linked list of size “n” for reversing it so time complexity will be O(n).

Space Complexity :
As we are creating a stack and storing “n” nodes values in it. Here “n” is the size of the linked list. So O(n) auxiliary space is used here.

Conclusion

  • We have seen five approaches to reverse a linked list.These are :
    • Iterative Method,
    • Recursive Method,
    • Tail Recursive Method,
    • Using Array,
    • Using Stack.
  • An iterative method is the best one for reversing the linked list under O(n) time complexity and O(1) space complexity.
  • Using the stack approach takes O(n) time and space for reversing the linked list.

Author

Latest articles

Largest Number Formed from an Array

Sindhuja Gudala

Fundamentals of Enhanced Interior Gateway Routing Protocol

Trapti Gupta

What is Network Hub?

Akshay Mishra