C++ Program to Reverse a Linked List

1. Introduction

A linked list is a linear data structure in which each element points to the next element in the sequence. One of the common operations we can perform on a linked list is reversing its elements. In this blog post, we'll see how to reverse a linked list in C++.

2. Program Overview

We will first create a singly linked list and then implement a function to reverse its elements. The method used will involve changing the next pointers of each node to point to its previous node.

Check out the C++ Program to Implement a Singly Linked List.

3. Code Program

#include <iostream>

// Define a Node for the linked list
class Node {
public:
    int data;       // Data contained in the node
    Node* next;     // Pointer to the next node

    // Constructor to initialize node data and next pointer
    Node(int val) : data(val), next(nullptr) {}
};

// Define a Singly Linked List
class LinkedList {
private:
    Node* head;     // Pointer to the start of the list

public:
    // Constructor to initialize an empty list with head as nullptr
    LinkedList() : head(nullptr) {}

    // Member functions of the linked list
    void insert(int val);        // Insert a node at the end of the list
    void display();              // Display the contents of the list
    void reverse();              // Reverse the linked list in place
};

// Function to insert a node at the end of the list
void LinkedList::insert(int val) {
    Node* newNode = new Node(val);   // Create a new node
    if (!head) {
        head = newNode;              // If list is empty, make the new node the head
        return;
    }
    Node* temp = head;
    while (temp->next) {
        temp = temp->next;           // Traverse to the end of the list
    }
    temp->next = newNode;            // Insert the new node at the end
}

// Function to display the contents of the list
void LinkedList::display() {
    Node* temp = head;
    while (temp) {
        std::cout << temp->data << " -> ";
        temp = temp->next;           // Move to the next node
    }
    std::cout << "NULL" << std::endl; // Mark the end of the list
}

// Function to reverse the linked list in place
void LinkedList::reverse() {
    Node* prev = nullptr;          // Previous pointer, initialized to nullptr
    Node* current = head;          // Current pointer, initialized to head
    Node* next = nullptr;          // Next pointer, initialized to nullptr
    while (current) {
        next = current->next;      // Store next node
        current->next = prev;      // Reverse current node's pointer
        prev = current;            // Move previous pointer to current node
        current = next;            // Move current pointer to next node
    }
    head = prev;                   // Reassign the head pointer to the last node of the original list
}

int main() {
    LinkedList list;                  // Create an empty list
    list.insert(10);                 // Insert values
    list.insert(20);
    list.insert(30);
    list.display();                  // Display the list
    list.reverse();                  // Reverse the list
    list.display();                  // Display the reversed list
    return 0;
}

Output:

10 -> 20 -> 30 -> NULL
30 -> 20 -> 10 -> NULL

4. Step By Step Explanation

The LinkedList class contains all the methods for basic linked list operations as well as a method to reverse the list.

1. The insert method appends a new node at the end of the list.

2. The display method traverses and prints the linked list from the head to the end.

3. The reverse method is where the magic happens. It uses three pointers: prev, current, and next. As we traverse the list, we change the next pointer of the current node to point to its previous node.

The main function demonstrates these methods. After inserting three nodes and displaying the list, we reverse the list and then display it again to show that the elements have been successfully reversed.