Java Program to Reverse a Linked List

Introduction

Reversing a linked list is a common problem in data structure manipulation. In a linked list, each node contains data and a reference (or pointer) to the next node in the sequence. Reversing a linked list involves changing the direction of the pointers so that the first node becomes the last, and the last node becomes the first.

Problem Statement

Create a Java program that:

• Defines a singly linked list.
• Reverses the linked list.
• Displays the linked list before and after reversal.

Example 1:

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

Example 2:

• Input: 10 -> 20 -> 30 -> 40
• Output: 40 -> 30 -> 20 -> 10

Solution Steps

1. Define the Node Class: Create a class to represent a node in the linked list, containing data and a reference to the next node.
2. Define the LinkedList Class: Create a class to manage the linked list, including methods to insert elements, reverse the list, and display the list.
3. Reverse the Linked List: Implement a method to reverse the linked list by changing the direction of the pointers.
4. Display the Linked List: Implement methods to display the linked list before and after reversal.

Java Program

Java Program to Reverse a Linked List

class Node {
    int data;
    Node next;

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

class LinkedList {
    Node head;

    // Method to insert a new node at the end of the list
    public void insert(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 next node
            current.next = previous; // Reverse the current node's pointer
            previous = current; // Move pointers one position ahead
            current = next;
        }
        head = previous; // Update 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 static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Insert elements into the linked list
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);

        // Display the original list
        System.out.println("Original Linked List:");
        list.display();

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

        // Display the reversed list
        System.out.println("Reversed Linked List:");
        list.display();
    }
}

Explanation

• Node Class: This class defines a node in the linked list. Each node has an integer data field and a next pointer that points to the next node in the list.

• LinkedList Class: This class manages the linked list and provides methods to insert nodes, reverse the list, and display the list.

  • insert(int data): Adds a new node with the given data at the end of the list.

  • reverse(): Reverses the linked list by changing the direction of the next pointers. The method uses three pointers (previous, current, next) to track the progress through the list and reverse the links between nodes.

  • display(): Prints the elements of the linked list from head to tail, followed by null to indicate the end of the list.

• Main Method: The main method demonstrates the functionality of the linked list by inserting elements, displaying the original list, reversing the list, and then displaying the reversed list.

Output Example

Example 1:

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

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

Example 2:

Original Linked List:
10 -> 20 -> 30 -> 40 -> null

Reversed Linked List:
40 -> 30 -> 20 -> 10 -> null

Conclusion

This Java program effectively demonstrates how to reverse a singly linked list. By manipulating the next pointers in each node, the list's order is reversed. The program provides clear methods for inserting elements, reversing the list, and displaying the list, making it a useful tool for understanding and working with linked lists in Java.