1. Introduction

A Linked List is a data structure where elements, known as nodes, are connected by pointers. Each node contains a data element and a next pointer which points to the subsequent node in the sequence. Reversing a linked list involves reconfiguring the next pointers so that the order of nodes in the list is reversed.

2. Program Steps

1. Initialize three pointers: prev, current, and next.

2. Traverse the list using the current pointer.

3. For each node:

a. Save its next node to the next pointer.

b. Change its next pointer to the prev.

c. Move the prev pointer to the current node.

d. Move the current pointer to the next node.

4. Reset the head of the linked list to the prev pointer.

3. Code Program

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class LinkedList {
    Node head;

    // Function to reverse the linked list
    void reverse() {
        Node prev = null;
        Node current = head;
        Node next = null;

        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
    }

    // Function to print the linked list
    void printList() {
        Node n = head;
        while (n != null) {
            System.out.print(n.data + " ");
            n = n.next;
        }
    }

    // Function to insert a new Node at the last
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }

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

        list.append(5);
        list.append(10);
        list.append(15);
        list.append(20);

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

        list.reverse();

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

Output:

Original Linked list:
5 10 15 20
Reversed Linked list:
20 15 10 5

4. Step By Step Explanation

1. A Node class is defined to create new nodes for the Linked List. Each node contains a data value and a next pointer which points to the subsequent node.

2. The LinkedList class provides methods to manipulate the linked list, including a reverse method to reverse the list.

3. Inside the reverse method, we iterate through the nodes of the linked list and change the direction of the next pointers to reverse the list.

4. In the main method:

a. A LinkedList object is created.

b. Nodes with values 5, 10, 15, and 20 are added to the list.

c. The original list is printed.

d. The list is reversed.

e. The reversed list is printed.

5. The output illustrates the linked list in its original order and its reversed order.

Understanding the procedure to reverse a Linked List is fundamental in data structure and algorithm topics, and it often serves as a base for many advanced algorithms and problem-solving tasks.