Reverse a linked list - Reverse a Singly Linked List

Problem Statement

The problem “reverse a linked list” states that we are given the head of the linked list. We have to reverse the linked list by changing the links between them and return the head of the reversed linked list.

Example

10->20->30->40->NULL

NULL<-10<-20<-30<-40

Explanation

We have reversed the linked list by changing the links between them. So the new linked list after performing reverse operation becomes 40->30->20->10->NULL.

Approach for reverse a linked list

Iterative approach

1. Initialize the current pointer as the head.
2. Initialize previous and the next pointer as NULL.
3. Run a loop till current points to NULL.
  1. Assign current’s next to the next pointer.
  2. Now assign the previous pointer to current’s next pointer.
  3. Assign current to previous next to current.
4. Assign head to previous.

Reverse a linked list

C++ code

#include <iostream>
using namespace std;
struct Node {
  int data;
  struct Node* next;
  Node(int data)
  {
    this->data = data;
    next = NULL;
  }
};
struct LinkedList {
  Node* head;
  LinkedList()
  {
    head = NULL;
  }
  void reverse()
  {
    Node* current = head;
    Node *prev = NULL, *next = NULL;
    while (current != NULL) {
      next = current->next;
      current->next = prev;
      prev = current;
      current = next;
    }
    head = prev;
  }
  void print()
  {
    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;
  }
};
int main()
{
  LinkedList ll;
  ll.push(40);
  ll.push(30);
  ll.push(20);
  ll.push(10);
  cout << "old linked list\n";
  ll.print();
  ll.reverse();
  cout << "\nnew Linked list \n";
  ll.print();
  return 0;
}

old linked list: 
10 20 30 40

new Linked list: 
40 30 20 10

Java code

class LinkedList { 
  static Node head; 
  static class Node { 
    int data; 
    Node next; 
    Node(int d) 
    { 
      data = d; 
      next = null; 
    } 
  } 
  Node reverse(Node node) 
  { 
    Node prev = null; 
    Node current = node; 
    Node next = null; 
    while (current != null) { 
      next = current.next; 
      current.next = prev; 
      prev = current; 
      current = next; 
    } 
    node = prev; 
    return node; 
  } 
  void printList(Node node) 
  { 
    while (node != null) { 
      System.out.print(node.data + " "); 
      node = node.next; 
    } 
  } 
  public static void main(String[] args) 
  { 
    LinkedList list = new LinkedList(); 
    list.head = new Node(10); 
    list.head.next = new Node(20); 
    list.head.next.next = new Node(30); 
    list.head.next.next.next = new Node(40); 
    System.out.println("old Linked list"); 
    list.printList(head); 
    head = list.reverse(head); 
    System.out.println(""); 
    System.out.println("new linked list "); 
    list.printList(head); 
  } 
}

old linked list: 
10 20 30 40

new Linked list: 
40 30 20 10

Complexity Analysis

Time Complexity

O(n) because we are traversing the linked list only once.

Space Complexity

O(1) because we are using space to store temporary variables only.

Recursive approach

We assign the last node as a head node by traversing through the linked list.
And link the last returned tail of the linked list with its previous node. This step is followed by recursively.

C++ code

#include <iostream> 
using namespace std; 
struct Node { 
  int data; 
  struct Node* next; 
  Node(int data) 
  { 
    this->data = data; 
    next = NULL; 
  } 
}; 
struct LinkedList { 
  Node* head; 
  LinkedList() 
  { 
    head = NULL; 
  } 
  Node* reverse(Node* node) 
  { 
    if (node == NULL) 
      return NULL; 
    if (node->next == NULL) { 
      head = node; 
      return node; 
    } 
    Node* node1 = reverse(node->next); 
    node1->next = node; 
    node->next = NULL; 
    return node; 
  } 
  /* Function to print linked list */
  void print() 
  { 
    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; 
  } 
}; 
int main() 
{ 
  LinkedList ll; 
  ll.push(40); 
  ll.push(30); 
  ll.push(20); 
  ll.push(10); 
  cout << "old linked list\n"; 
  ll.print(); 
  ll.reverse(ll.head); 
  cout << "\n new Linked list \n"; 
  ll.print(); 
  return 0; 
}

old linked list: 
10 20 30 40

new Linked list: 
40 30 20 10

Java code to reverse a linked list

import java.io.BufferedWriter; 
import java.io.IOException; 
import java.io.OutputStreamWriter; 
import java.util.Scanner; 
class ReverseLinkedListRecursive { 
    static class Node { 
    public int data; 
    public Node next; 
    public Node(int nodeData) { 
      this.data = nodeData; 
      this.next = null; 
    } 
  } 
  static class LinkedList { 
    public Node head; 
    public LinkedList() { 
      this.head = null; 
    } 
    public void insertNode(int nodeData) { 
      Node node = new Node(nodeData); 
      if (this.head != null) { 
        node.next = head; 
      } 
      this.head = node; 
    } 
  } 
  public static void printSinglyLinkedList(Node node, 
            String sep) throws IOException { 
    while (node != null) { 
      System.out.print(String.valueOf(node.data) + sep); 
      node = node.next; 
    } 
  } 
  static Node reverse(Node head) { 
    if(head == null) { 
      return head; 
    } 
    if(head.next == null) { 
      return head; 
    } 
    Node newHeadNode = reverse(head.next); 
    head.next.next = head; 
    head.next = null; 
    return newHeadNode; 
  } 
  private static final Scanner scanner = new Scanner(System.in); 
  public static void main(String[] args) throws IOException { 
      LinkedList llist = new LinkedList(); 
    
      llist.insertNode(40); 
      llist.insertNode(30); 
      llist.insertNode(20); 
      llist.insertNode(10); 
      
      System.out.println("old linked list:"); 
      printSinglyLinkedList(llist.head, " "); 
      
      System.out.println(); 
      System.out.println("new Linked list:"); 
      Node llist1 = reverse(llist.head); 
      printSinglyLinkedList(llist1, " "); 
    scanner.close(); 
  } 
}

old linked list: 
10 20 30 40

new Linked list: 
40 30 20 10

Complexity Analysis

Time Complexity

O(n) because we are traversing the linked list only once.

Space Complexity

O(n) because we are using space to store temporary variables on the compiler stack. These temporary variables are dependent on the number of nodes in the linked list.

Tail recursive approach

This approach is a type of recursion which is also known as tail recursion. In the tail recursion, we need not go back to the function which has initiated its call. We pass the result values of the previous call as a parameter to the new function call. This is useful at the compiler level also because we need not maintain the system stack to store the values of previous calls. This is also helpful in preventing from stack overflow.

C++ code

#include <bits/stdc++.h> 
using namespace std; 
struct Node { 
  int data; 
  struct Node* next; 
}; 
void reverseUtil(Node* curr, Node* prev, Node** head); 
void reverse(Node** head) 
{ 
  if (!head) 
    return; 
  reverseUtil(*head, NULL, head); 
} 
void reverseUtil(Node* curr, Node* prev, Node** head) 
{ 
  if (!curr->next) { 
    *head = curr; 
    curr->next = prev; 
    return; 
  } 
  Node* next = curr->next; 
  curr->next = prev; 
  reverseUtil(next, curr, head); 
} 
Node* newNode(int key) 
{ 
  Node* temp = new Node; 
  temp->data = key; 
  temp->next = NULL; 
  return temp; 
} 
void printlist(Node* head) 
{ 
  while (head != NULL) { 
    cout << head->data << " "; 
    head = head->next; 
  } 
  cout << endl; 
} 
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); 
  cout << "old linked list\n"; 
  printlist(head1); 
  reverse(&head1); 
  cout << "\nnew linked list\n"; 
  printlist(head1); 
  return 0; 
}

old linked list
1 2 3 4 5 6 7 8

new linked list
8 7 6 5 4 3 2 1

Java code

class LinkedList { 
  static Node head; 
  static class Node { 
    int data; 
    Node next; 
    Node(int d) 
    { 
      data = d; 
      next = null; 
    } 
  } 
  Node reverseUtil(Node curr, Node prev) 
  { 
    if (curr.next == null) { 
      head = curr; 
      curr.next = prev; 
      return head; 
    } 
    Node next1 = curr.next; 
    curr.next = prev; 
    reverseUtil(next1, curr); 
    return head; 
  } 
  void printList(Node node) 
  { 
    while (node != null) { 
      System.out.print(node.data + " "); 
      node = node.next; 
    } 
  } 
  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("Old Linked list "); 
    list.printList(head); 
    Node res = list.reverseUtil(head, null); 
    System.out.println(""); 
    System.out.println(""); 
    System.out.println("new linked list "); 
    list.printList(res); 
  } 
}

old linked list 
1 2 3 4 5 6 7 8
new linked list 
8 7 6 5 4 3 2 1

Complexity Analysis

Time Complexity

O(n) because we are traversing the linked list only once.

Space Complexity

O(n) because we are using space to store temporary variables only on the compiler stack. These temporary variables are dependent on the number of nodes in the linked list.

References