Java Program to Reverse a Linked List

Introduction

Reversing a linked list involves changing the direction of the links between nodes so that the last node becomes the first, and the first node becomes the last. This operation is fundamental in various applications, such as reversing the order of elements or preparing for specific algorithms. This guide will walk you through writing a Java program that reverses a singly linked list.

Problem Statement

Create a Java program that:

• Implements a singly linked list.
• Reverses the linked list in place.
• Displays the linked list before and after the reversal.

Example:

• Input: 1 -> 2 -> 3 -> 4 -> 5
• Output: 5 -> 4 -> 3 -> 2 -> 1

Solution Steps

1. Create a Node Class: Define a Node class to represent each element in the linked list.
2. Create a LinkedList Class: Define a LinkedList class with methods to add elements, display the list, and reverse the list.
3. Reverse the Linked List: Implement a method to reverse the linked list by adjusting the pointers between nodes.
4. Display the Linked List: Print the linked list before and after reversing.

Java Program

// Java Program to Reverse a Linked List
// Author: https://www.rameshfadatare.com/

class Node {
    int data;
    Node next;

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

class LinkedList {
    Node head;

    // Method to add a new node at the end of the list
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // Method to reverse the linked list
    public void reverse() {
        Node previous = null;
        Node current = head;
        Node next = null;

        while (current != null) {
            next = current.next; // Store the next node
            current.next = previous; // Reverse the link
            previous = current; // Move previous to this node
            current = next; // Move to the next node
        }
        head = previous; // Reset the head to the new first node
    }

    // Method to display the linked list
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class ReverseLinkedList {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Adding elements to the linked list
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        System.out.println("Original Linked List:");
        list.display();

        // Reversing the linked list
        list.reverse();

        System.out.println("Reversed Linked List:");
        list.display();
    }
}

Explanation

Node Class

• The Node class represents a single node in the linked list. Each node contains data and a reference to the next node in the list.

LinkedList Class

• The LinkedList class manages the linked list:
  • add() Method: Adds a new node to the end of the list.
  • reverse() Method: Reverses the linked list in place by adjusting the next pointers of each node.
  • display() Method: Prints the elements of the linked list in order.

Reversing the Linked List

• The reverse() method uses three pointers: previous, current, and next.
  • It iterates through the list, reversing the direction of the next pointers.
  • After the loop, the head pointer is updated to point to the last node, which becomes the new first node in the reversed list.

Output Example

Original Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> null
Reversed Linked List:
5 -> 4 -> 3 -> 2 -> 1 -> null

Conclusion

This Java program demonstrates how to reverse a singly linked list by adjusting the pointers between nodes. The program covers essential concepts such as linked list manipulation, node traversal, and pointer management. This exercise is valuable for understanding how to work with linked lists and perform in-place modifications in Java programming.