Tuesday, 13 February 2018

Java Program to Reverse a Linked List using Recursion and Loops

           In previous post, we learned about Internal working of LinkedList in Java. In this, we can write a code to reverse a linkedlist using recursion and iterative way.

ReverseLinkedList.java:--


 package com.practice;

 public class ReverseLinkedList {
       static Node head;
  
       static class Node {
  
             int data;
             Node next;
  
             Node(int d) {
                 data = d;
                 next = null;
             }
        }
  
        // using iterative way
        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;
        }
    
        // using recursive
        Node reverseUtil(Node curr, Node prev) {
             if (curr.next == null) {
                  head = curr;
  
                  curr.next = prev;
                  return null;
              }
  
              Node next1 = curr.next;
  
               /* and update next ..*/
              curr.next = prev;
  
              reverseUtil(next1, curr);
              return head;
        }
  
         // prints content of linked list
        void printList(Node node) {
              while (node != null) {
                  System.out.print(node.data + " ");
                  node = node.next;
              }
         }
  
         public static void main(String[] args) {
                  ReverseLinkedList list = new ReverseLinkedList();
                  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);
       
  
                  System.out.println("Original Linked list ");
                  list.printList(head);
                  Node res = list.reverseUtil(head, null);
                  System.out.println("");
                  System.out.println("Reversed linked list ");
                  list.printList(res);
      
                  System.out.println("");
                  System.out.println("Original Linked list2 ");
                  list.printList(head);
                  Node result = list.reverse(head);
                  System.out.println("");
                  System.out.println("Reversed linked list2 ");
                  list.printList(result);
        }
 }

Output:--   Original Linked list
                   1 2 3 4
                   Reversed linked list
                   4 3 2 1
                   Original Linked list2
                   4 3 2 1
                   Reversed linked list2
                   1 2 3 4


Related Post:--
1) Internal Implementation of LinkedList in Java
2) Internal implementation of ArrayList in Java
3) Java Program for Bubble Sort in Ascending and Descending order
4) Java Program to Sort ArrayList of Custom Objects By Property using Comparator interface
5) How to Remove duplicates from ArrayList in Java