Question

Describe in detail an algorithm for reversing a singly linked list L using only a constant amount of additional space.

Please provide pseudocode for Java.

Answer 1

//java program to reverse a linked list
import java.io.*;
import java.util.*;

class ReverseLinkedList {

   static Node head;

   static class Node
   {

       int val;
       Node nxt;

       Node(int element)
       {
           val = element;
           nxt = null;
       }
   }

   //method to reverse the linked list
   Node reverse(Node node)
   {
       Node prev = null;
       Node curr = node;
       Node nxt = null;
       while (curr != null)
       {
           nxt = curr.nxt;
           curr.nxt = prev;
           prev = curr;
           curr = nxt;
       }
       node = prev;
       return node;
   }

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

   public static void main(String[] args)
   {
       ReverseLinkedList obj = new ReverseLinkedList();
       obj.head = new Node(5);
       obj.head.nxt = new Node(10);
       obj.head.nxt.nxt = new Node(4);
       obj.head.nxt.nxt.nxt = new Node(2);
      
       System.out.println("Given Linked list");
       obj.display(head);
       head = obj.reverse(head);
       System.out.println("");
       System.out.println("Reversed linked list ");
       obj.display(head);
       System.out.println("");
   }
}

output -