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

Friday, September 4, 2020

Linked list nth last element

 September 04, 2020     Programming problems in CPP     No comments   

Write a program to find in a linked list nth last element

The approach:-
  1. Maintain 2 pointers to head of the list.
  2. Move 1st pointer n - 1 elements.
  3. Now move both the pointers until one of them hits the end of list.
  4. Return the other pointer which would point in the linked list nth element from last.

C++ program to find a linked list nth last element

#include <iostream>
using namespace std;

// Node class
class Node {
  private:
    int mData;
    Node* mNext;
  public:
    Node() { mNext = NULL; }
    ~Node() {}
    int data() { return mData; }
    Node* next() { return mNext; }
    void setData(int data) { mData = data; }
    void setNext(Node* next) { mNext = next; }
};

// List class
class List {
  private:
    Node* head;
  public:
    List() { head = NULL; }

    ~List() {}

    void addNode(int data) {
        if ( head == NULL ) {
            Node* tmp = new Node();
            tmp->setData(data);
            head = tmp;
        }
        else {
            Node* tmp = head;
            while ( tmp->next() != NULL )
                    tmp = tmp->next();

            Node* tmp1 = new Node();
            tmp1->setData(data);
            tmp->setNext(tmp1);
        }
    }

    friend ostream& operator << (ostream& o, const List& l) {
        Node* tmp = l.head;
        while ( tmp != NULL ) {
                cout << tmp->data() << " ";
                tmp = tmp->next();
        }
        return o;
    }

    Node* fromLast(int n) {
        // 2 pointers to the list head
        Node* tmp1 = head;
        Node* tmp2 = head;

        // Move second pointer 'n-1' places from start
        int count = n - 1;
        while ( tmp2 != NULL && count-- >= 0 ) {
            tmp2 = tmp2->next();
        }

        // Move both pointers till end of list
        while ( tmp2 != NULL ) {
            tmp2 = tmp2->next();
            tmp1 = tmp1->next();
        }

        // return the first pointer
        return tmp1;
    }
};

// Test program
int main() {
    List* l = new List();

    // Add some random nodes
    for ( int i = 1; i <= 10; i++ )
            l->addNode(i*100);

    cout << *l << endl;
    cout << l->fromLast(4)->data() << endl;

    delete l;
}
Output:-
100 200 300 400 500 600 700 800 900 1000
700
  • 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