Home » C++ programs » D.S. programs

Delete N nodes after M nodes of a linked list using C++ program

In this article, we are going to learn how to delete N nodes after M nodes of a Linked List using C++ program?
Submitted by Souvik Saha, on May 06, 2019

Problem statement:

Given a Linked List, we have to delete N numbers of nodes after the M numbers of nodes.

Example:

    Input: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10
    N=2, M=3
    Output: 1 → 2 → 3 → 6 → 7 → 8

    Input: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11
    N=3, M=3
    Output: 1 → 2 → 3 → 7 → 8 → 9

Algorithm:

To solve that problem we simply use the Brute-Force method. We traverse the linked list from the head node and delete N nodes after traversing M nodes. If there are less than N nodes to delete then we simply delete that nodes and stop traversing.

C++ implementation:

#include <bits/stdc++.h>
using namespace std;

struct node {
    int data;
    node* next;
};

//Create a new node
struct node* create_node(int x)
{
    struct node* temp = new node;
    temp->data = x;
    temp->next = NULL;
    return temp;
}

//Enter the node into the linked list
void push(node** head, int x)
{
    struct node* store = create_node(x);
    if (*head == NULL) {
        *head = store;
        return;
    }
    struct node* temp = *head;
    while (temp->next) {
        temp = temp->next;
    }
    temp->next = store;
}

//Reverse the linked list
void delete_node(node* head, int m, int n)
{
    struct node* temp = head;
    int count = 1;
    while (1) {
        while (temp && count < m) {
            temp = temp->next;
            count++;
        }
        if (temp == NULL || temp->next == NULL) {
            return;
        }
        count = 1;
        struct node* store = temp;
        temp = temp->next;
        while (temp && count < n) {
            temp = temp->next;
            count++;
        }
        if (temp == NULL) {
            return;
        }
        store->next = temp->next;
        temp = temp->next;
    }
}

//Print the list
void print(node* head)
{
    struct node* temp = head;
    while (temp) {
        cout << temp->data << " ";
        temp = temp->next;
    }
}

int main()
{
    struct node* l = NULL;
    push(&l, 1);
    push(&l, 2);
    push(&l, 3);
    push(&l, 4);
    push(&l, 5);
    push(&l, 6);
    cout << "Before the delete operation" << endl;
    print(l);
    delete_node(l, 3, 2);
    cout << "\nAfter the delete operation" << endl;
    print(l);

    return 0;
}

Output

Before the delete operation
1 2 3 4 5 6
After the delete operation
1 2 3 6





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.




Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.