Java Program to Reverse a Linked List

Reversing a linked list is a common data structure problem that is often asked during technical interviews. It tests one's understanding of linked list operations and pointer manipulations. In this blog post, we'll dive into how to reverse a singly linked list using Java. 

What is a Linked List? 

A linked list is a data structure in which elements are called nodes and these nodes are connected together in a linear fashion. Each node contains two main parts: data and a reference (or pointer) to the next node in the sequence. 

Step-by-Step Solution

1. Define the Node Class 

Before we proceed with the reversal logic, we need to define the structure of a Node in our linked list.

class Node {
    int data;
    Node next;

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

2. Reverse the Linked List 

The idea is to traverse the list and change the next of each Node to point to its previous node. We'll make use of three-pointers: previous, current, and next.

public Node reverse(Node head) {
    Node previous = null;
    Node current = head;
    Node next = null;

    while (current != null) {
        next = current.next;  // Store next node
        current.next = previous; // Change next of current node
        previous = current;  // Move previous to this node
        current = next;  // Move to next node
    }
    head = previous;  // Change head to the last node in the original list
    return head;
}

3. Test the Code 

Now, we can test our reversal logic on a simple linked list.

public static void main(String[] args) {
    Node head = new Node(1);
    head.next = new Node(2);
    head.next.next = new Node(3);
    head.next.next.next = new Node(4);

    System.out.println("Original Linked List:");
    printList(head);

    head = reverse(head);

    System.out.println("\nReversed Linked List:");
    printList(head);
}

public static void printList(Node head) {
    Node temp = head;
    while (temp != null) {
        System.out.print(temp.data + " ");
        temp = temp.next;
    }
}

Complete Code: Java Program to Reverse a Linked List

class Node {
    int data;
    Node next;

    // Constructor to initialize the node with data
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class ReverseLinkedList {
    
    // Function to reverse the linked list
    public static Node reverse(Node head) {
        Node previous = null;
        Node current = head;
        Node next = null;

        while (current != null) {
            next = current.next;  // Store next node
            current.next = previous; // Reverse current node's pointer
            previous = current;  // Move previous to this node
            current = next;  // Move to next node
        }
        head = previous;  // Move head to the last node in the original list
        return head;
    }
    
    // Utility function to print the linked list
    public static void printList(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);

        System.out.println("Original Linked List:");
        printList(head);

        head = reverse(head);

        System.out.println("Reversed Linked List:");
        printList(head);
    }
}

Output:

Original Linked List:
1 2 3 4 
Reversed Linked List:
4 3 2 1 

Explanation: 

We start with the head pointing to 1, and our goal is to reverse the pointers. 

After the first iteration, 1 will point to null, and the previous will point to 1. 

After the second iteration, 2 will point to 1, and the previous will point to 2. 

This continues until we've reversed the entire list. 

Note: This operation does not rearrange the nodes but only changes the direction of the pointers. 

By understanding and mastering this fundamental linked list operation, one can confidently tackle more complex linked list problems and operations. It forms foundational knowledge for algorithms and data structures in computer science.