StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Tuesday, July 10, 2012

Reverse a linked list

 July 10, 2012     Programming problems in CPP     No comments   

Write a program to construct and reverse a linked list

We write an iterative approach to reverse a linked list. The approach is to start from the head node and prepend the subsequent nodes so that the list gets reversed. 3 pointers are used to do the list manipulation.

C++ program to reverse a linked list

#include <iostream>
using namespace std;

// List nodeclass
class Node {
public:
    int data;
    Node* next;
};

// Linked list class
class List {
public:
    List() { head = NULL; }
    ~List() {}
    void addNode(int val);
    void reverse();
    void print();

private:
    Node* head;
};

// Function to add a node to the list
void List::addNode(int val)
{
    Node* temp = new Node();
    temp->data = val;
    temp->next = NULL;

    if ( head == NULL ) {
        head = temp;
    }
    else {
        Node* temp1 = head;
        while ( temp1->next != NULL )
            temp1 = temp1->next;
        temp1->next = temp;
    }
}

// Iterative function to reverse a list
void List::reverse()
{
    Node* n1 = head;
    Node* n2 = NULL;
    Node* n3 = NULL;
    while ( n1 != NULL )
    {
        head = n1;
        n2 = n1->next;
        n1->next = n3;
        n3 = n1;
        n1 = n2;
    }
}

void List::print()
{
    Node* temp = head;
    while ( temp != NULL ) {
        cout << temp->data << " ";         
        temp = temp->next;
    }
    cout << endl; 
} 

// Test program 
int main() {    
    List* list = new List();     
    list->addNode(100);
    list->addNode(200);
    list->addNode(300);
    list->addNode(400);
    list->addNode(500);
    list->print();
    list->reverse();
    list->print();
    delete list;
}
Output:-
100 200 300 400 500
500 400 300 200 100
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk