Blog

Reverse a Linked List in Java


In this tutorial, we will discuss the different algorithms for Reversing a linked list using Java.

Example :

Input List:

Output List:

In this tutorial ,we will reverse a LinkedList by using two ways:

  • Iterative way
  • Recursive way

Example – Program to Reverse a Linked List using Iterative way

To reverse a LinkedList repeatedly, you must store references to the previous and next items. This ensures that the exchange of memory address pointers to the next item in the LinkedList will not be lost.

public class ReverseLinkedList {

  public Node head;

  public static class Node {

    Node next;

    Object data;

    Node(Object data) {
      this.data = data;
      next = null;
    }
  }

  public static void main(String[] args) {
    ReverseLinkedList myLinkedList = new ReverseLinkedList();
    myLinkedList.head = new Node(3);
    myLinkedList.head.next = new Node(4);
    myLinkedList.head.next.next = new Node(5);
    System.out.print("Original linked list : ");
    printLinkedList(myLinkedList);
    reverseLinkedList(myLinkedList);
    System.out.print("Reverse  linked list : ");
    printLinkedList(myLinkedList);

  }

  public static void printLinkedList(ReverseLinkedList linkedList) {
    Node h = linkedList.head;
    while (linkedList.head != null) {
      System.out.print(linkedList.head.data + " ");
      linkedList.head = linkedList.head.next;
    }
    System.out.println();
    linkedList.head = h;
  }

  public static void reverseLinkedList(ReverseLinkedList linkedList) {
    Node previous = null;
    Node current = linkedList.head;
    Node next;
    while (current != null) {
      next = current.next;
      current.next = previous;
      previous = current;
      current = next;
    }
    linkedList.head = previous;
  }

}

Output

Original linked list : 3 4 5
Reverse linked list : 5 4 3

Example – Program to Reverse a Linked List using Recursive way

public class ReverseLinkedList {

  public Node head;

  public static class Node {

    Node next;

    Object data;

    Node(Object data) {
      this.data = data;
      next = null;
    }
  }

  public static void main(String[] args) {
    ReverseLinkedList myLinkedList = new ReverseLinkedList();
    myLinkedList.head = new Node(3);
    myLinkedList.head.next = new Node(4);
    myLinkedList.head.next.next = new Node(5);
    System.out.print("Original linked list : ");
    printLinkedList(myLinkedList);
    myLinkedList.head = recursiveReverse(myLinkedList.head);
    System.out.print("Reverse  linked list : ");
    printLinkedList(myLinkedList);

  }

  public static void printLinkedList(ReverseLinkedList linkedList) {
    Node h = linkedList.head;
    while (linkedList.head != null) {
      System.out.print(linkedList.head.data + " ");
      linkedList.head = linkedList.head.next;
    }
    System.out.println();
    linkedList.head = h;
  }

  public static Node recursiveReverse(Node head) {
    Node first;

    if (head == null || head.next == null)
      return head;

    first = recursiveReverse(head.next);
    head.next.next = head;
    head.next = null;

    return first;
  }

}

Output

Original linked list : 3 4 5
Reverse linked list : 5 4 3
Tags: ,