Reverse a Linked List | DSA in C++ - Software Development PDF Download

Introduction

In this article, we will explore the concept of reversing a linked list in C++. Linked lists are fundamental data structures in computer science, and understanding how to reverse them is an essential skill. We will cover the theory behind the reversal process and provide easy-to-understand code examples with explanations. Additionally, we will conclude with sample problems and solutions to reinforce your understanding.

What is a Linked List?

A linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a pointer/reference to the next node in the sequence. It allows dynamic memory allocation and efficient insertion/deletion operations.

Reversing a Linked List: Theory

Reversing a linked list involves changing the direction of the pointers, essentially flipping the order of the nodes. The first node becomes the last node, and the last node becomes the first node.
To reverse a linked list, we need to update the next pointers of each node, pointing them in the opposite direction. We also need to keep track of three pointers: the current node, the previous node, and the next node.

Reversing a Linked List: Implementation in C++

Let's now dive into the implementation of the reverse operation in C++. We will create a simple linked list class and provide a function to reverse the list.

#include <iostream>

// Node structure

struct Node {

    int data;

    Node* next;

};

// Linked list class

class LinkedList {

private:

    Node* head;

public:

    LinkedList() : head(nullptr) {}

    // Function to reverse the linked list

    void reverse() {

        Node* current = head;

        Node* previous = nullptr;

        Node* next = nullptr;

        while (current != nullptr) {

            next = current->next;

            current->next = previous;

            previous = current;

            current = next;

        }

        head = previous;

    }

    // Function to insert a new node at the beginning of the linked list

    void insert(int data) {

        Node* newNode = new Node;

        newNode->data = data;

        newNode->next = head;

        head = newNode;

    }

    // Function to display the linked list

    void display() {

        Node* temp = head;

        while (temp != nullptr) {

            std::cout << temp->data << " ";

            temp = temp->next;

        }

        std::cout << std::endl;

    }

};

Code Examples and Explanation

Now, let's see how the reverse function works with some example code and output.

int main() {

    LinkedList myList;

    // Inserting elements into the linked list

    myList.insert(5);

    myList.insert(10);

    myList.insert(15);

    myList.insert(20);

    std::cout << "Original list: ";

    myList.display();

    // Reversing the linked list

    myList.reverse();

    std::cout << "Reversed list: ";

    myList.display();

    return 0;

}

Output:

Original list: 20 15 10 5

Reversed list: 5 10 15 20

Explanation:

• We create a linked list object named 'myList' and insert four elements: 5, 10, 15, and 20.
• The original list is displayed using the 'display' function.
• The 'reverse' function is called to reverse the list.
• The reversed list is displayed using the 'display' function.

Sample Problems and Solutions

Here are some sample problems to further practice reversing a linked list:

Problem 1: Reverse a given linked list and return the new head.

Node* reverseList(Node* head) {

    // Implementation here (similar to the reverse function in LinkedList class)

}

Problem 2: Given a linked list, reverse the list in groups of size k.

Node* reverseInGroups(Node* head, int k) {

    // Implementation here (reverse each group of size k)

}

Conclusion

Reversing a linked list is a common operation that requires understanding the concept of changing pointers to flip the order of nodes. We covered the theory behind reversing a linked list and provided an easy-to-understand implementation in C++. Additionally, we presented code examples with explanations and offered sample problems for further practice. Mastering this skill will help you grasp the fundamentals of linked lists and enhance your understanding of data structures and algorithms in C++.