Reverse a Singly Linked List in C++

This program demonstrates how to reverse a singly linked list in C++. The structure of the program is broken down into the following parts:

• Definition of a singly linked list node.
• Function to reverse the linked list.
• Helper functions to create and display the linked list.
• The main function to test the reversal.

Program Structure

1. Node Definition

Each node in a singly linked list contains a value and a pointer to the next node. The structure is defined as follows:

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

2. Reverse Function

This function reverses the linked list by iterating through the list and adjusting the pointers. It uses three pointers: prev, current, and next. The algorithm is as follows:

• Initialize prev to nullptr and current to the head of the list.
• Iterate through the list, setting next to current->next.
• Set current->next to prev to reverse the link.
• Move prev and current one step forward.
• Continue until the list is fully reversed.
• Finally, set the head of the list to prev.

Node* reverseList(Node* head) {
    Node* prev = nullptr;
    Node* current = head;
    Node* next = nullptr;

    while (current != nullptr) {
        next = current->next;   // Store next node
        current->next = prev;    // Reverse the current node's pointer
        prev = current;           // Move pointers one position ahead
        current = next;
    }

    return prev; // New head of the reversed list
}

3. Helper Functions

These functions assist in creating and displaying the linked list. push() inserts a new node at the beginning of the list, and printList() prints all the elements of the list.

void push(Node** head_ref, int new_data) {
    Node* new_node = new Node(new_data);
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

void printList(Node* node) {
    while (node != nullptr) {
        std::cout << node->data << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

4. Main Function

The main function tests the linked list reversal by creating a list, printing it, reversing it, and then printing the reversed list.

int main() {
    Node* head = nullptr;

    // Create linked list 1->2->3->4->5
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);

    std::cout << "Original List: ";
    printList(head);

    head = reverseList(head);

    std::cout << "Reversed List: ";
    printList(head);

    return 0;
}

Explanation

The program begins by defining a Node structure to represent each element in the singly linked list. The reverseList() function takes the head of the linked list and reverses the order of the nodes by manipulating the pointers. The helper functions push() and printList() make it easy to build and display the linked list.

In the main() function, we create a sample linked list, display it, reverse it using the reverseList() function, and then display the reversed list.

Output

Running this program will produce the following output:

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

This demonstrates that the list has been successfully reversed.