Рубрики

Удалить N узлов после M узлов связанного списка

При наличии связанного списка и двух целых чисел M и N. Пройдите по связанному списку так, чтобы вы сохранили M узлов, затем удалили следующие N узлов, продолжайте то же самое до конца связанного списка.

Уровень сложности: Новичок

Примеры:

Input:
M = 2, N = 2
Linked List: 1->2->3->4->5->6->7->8
Output:
Linked List: 1->2->5->6

Input:
M = 3, N = 2
Linked List: 1->2->3->4->5->6->7->8->9->10
Output:
Linked List: 1->2->3->6->7->8

Input:
M = 1, N = 1
Linked List: 1->2->3->4->5->6->7->8->9->10
Output:
Linked List: 1->3->5->7->9

Основная часть проблемы заключается в поддержании надлежащих связей между узлами, убедитесь, что все угловые случаи обрабатываются. Ниже приведена реализация C функции skipMdeleteN (), которая пропускает M узлов и удаляет N узлов до конца списка. Предполагается, что M не может быть 0.

C ++

// C ++ программа для удаления N узлов
// после M узлов связанного списка
#include <bits/stdc++.h>

using namespace std;

  
// Узел связанного списка

class Node 

    public:

    int data; 

    Node *next; 

}; 

  
/ * Функция для вставки узла в начале * /

void push(Node ** head_ref, int new_data) 

    / * выделить узел * /

    Node* new_node = new Node();

  

    / * вставить данные * /

    new_node->data = new_data; 

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref); 

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref) = new_node; 

  
/ * Функция для печати связанного списка * /

void printList(Node *head) 

    Node *temp = head; 

    while (temp != NULL) 

    

        cout<<temp->data<<" "

        temp = temp->next; 

    

    cout<<endl; 

  
// Функция для пропуска M узлов, а затем
// удаляем N узлов связанного списка.

void skipMdeleteN(Node *head, int M, int N) 

    Node *curr = head, *t; 

    int count; 

  

    // Основной цикл, который проходит

    // через весь список

    while (curr) 

    

        // Пропустить M узлов

        for (count = 1; count < M && 

                curr!= NULL; count++) 

            curr = curr->next; 

  

        // Если мы достигли конца списка, вернемся

        if (curr == NULL) 

            return

  

        // Начать со следующего узла и удалить N узлов

        t = curr->next; 

        for (count = 1; count<=N && t!= NULL; count++) 

        

            Node *temp = t; 

            t = t->next; 

            free(temp); 

        

          

        // Связать предыдущий список с остальными узлами

        curr->next = t; 

  

        // Установить текущий указатель для следующей итерации

        curr = t; 

    

  
// Код драйвера

int main() 

    / * Создать следующий связанный список

    1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9-> 10 * /

    Node* head = NULL; 

    int M=2, N=3; 

    push(&head, 10); 

    push(&head, 9); 

    push(&head, 8); 

    push(&head, 7); 

    push(&head, 6); 

    push(&head, 5); 

    push(&head, 4); 

    push(&head, 3); 

    push(&head, 2); 

    push(&head, 1); 

  

    cout << "M = " << M<< " N = " << N << "\nGiven Linked list is :\n"

    printList(head); 

  

    skipMdeleteN(head, M, N); 

  

    cout<<"\nLinked list after deletion is :\n"

    printList(head); 

  

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// C программа для удаления N узлов после M узлов связанного списка
#include <stdio.h>
#include <stdlib.h>

  
// Узел связанного списка

struct Node

{

    int data;

    struct Node *next;

};

  
/ * Функция для вставки узла в начале * /

void push(struct Node ** head_ref, int new_data)

{

    / * выделить узел * /

    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

  

    / * вставить данные * /

    new_node->data  = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

    / * переместить голову, чтобы указать на новый узел * /

    (*head_ref)  = new_node;

}

  
/ * Функция для печати связанного списка * /

void printList(struct Node *head)

{

    struct Node *temp = head;

    while (temp != NULL)

    {

        printf("%d ", temp->data);

        temp = temp->next;

    }

    printf("\n");

}

  
// Функция для пропуска M узлов, а затем удаления N узлов связанного списка.

void skipMdeleteN(struct Node  *head, int M, int N)

{

    struct Node *curr = head, *t;

    int count;

  

    // Основной цикл, который проходит через весь список

    while (curr)

    {

        // Пропустить M узлов

        for (count = 1; count<M && curr!= NULL; count++)

            curr = curr->next;

  

        // Если мы достигли конца списка, вернемся

        if (curr == NULL)

            return;

  

        // Начать со следующего узла и удалить N узлов

        t = curr->next;

        for (count = 1; count<=N && t!= NULL; count++)

        {

            struct Node *temp = t;

            t = t->next;

            free(temp);

        }

        curr->next = t; // Связать предыдущий список с остальными узлами

  

        // Установить текущий указатель для следующей итерации

        curr = t;

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    / * Создать следующий связанный список

      1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9-> 10 * /

    struct Node* head = NULL;

    int M=2, N=3;

    push(&head, 10);

    push(&head, 9);

    push(&head, 8);

    push(&head, 7);

    push(&head, 6);

    push(&head, 5);

    push(&head, 4);

    push(&head, 3);

    push(&head, 2);

    push(&head, 1);

  

    printf("M = %d, N = %d \nGiven Linked list is :\n", M, N);

    printList(head);

  

    skipMdeleteN(head, M, N);

  

    printf("\nLinked list after deletion is :\n");

    printList(head);

  

    return 0;

}

Джава

// Java программа для удаления N узлов
// после M узлов связанного списка

import java.util.*;

  

class GFG

{

  
// Узел связанного списка

static class Node 

    int data; 

    Node next; 

}; 

  
/ * Функция для вставки узла в начале * /

static Node push( Node head_ref, int new_data) 

    / * выделить узел * /

    Node new_node = new Node(); 

  

    / * вставить данные * /

    new_node.data = new_data; 

  

    / * связать старый список с новым узлом * /

    new_node.next = (head_ref); 

  

    / * переместить голову, чтобы указать на новый узел * /

    (head_ref) = new_node;

      

    return head_ref;

  
/ * Функция для печати связанного списка * /

static void printList( Node head) 

    Node temp = head; 

    while (temp != null

    

        System.out.printf("%d ", temp.data); 

        temp = temp.next; 

    

    System.out.printf("\n"); 

  
// Функция для пропуска M узлов, а затем
// удаляем N узлов связанного списка.

static void skipMdeleteN( Node head, int M, int N) 

    Node curr = head, t; 

    int count; 

  

    // Основной цикл, который проходит

    // через весь список

    while (curr!=null

    

        // Пропустить M узлов

        for (count = 1; count < M && curr != null; count++) 

            curr = curr.next; 

  

        // Если мы достигли конца списка, вернемся

        if (curr == null

            return

  

        // Начать со следующего узла и удалить N узлов

        t = curr.next; 

        for (count = 1; count <= N && t != null; count++) 

        

            Node temp = t; 

            t = t.next; 

        

          

        // Связать предыдущий список с остальными узлами

        curr.next = t; 

  

        // Установить текущий указатель для следующей итерации

        curr = t; 

    

  
// Код драйвера

public static void main(String args[])

    / * Создать следующий связанный список

    1.2.3.4.5.6.7.8.9.10 * /

    Node head = null

    int M=2, N=3

    head=push(head, 10); 

    head=push(head, 9); 

    head=push(head, 8); 

    head=push(head, 7); 

    head=push(head, 6); 

    head=push(head, 5); 

    head=push(head, 4); 

    head=push(head, 3); 

    head=push(head, 2); 

    head=push(head, 1); 

  

    System.out.printf("M = %d, N = %d \nGiven"

                        "Linked list is :\n", M, N); 

    printList(head); 

  

    skipMdeleteN(head, M, N); 

  

    System.out.printf("\nLinked list after deletion is :\n"); 

    printList(head); 


}

  
// Этот код предоставлен Арнабом Кунду

питон

# Программа Python для удаления M узлов после N узлов

  
# Класс узла

class Node:

  

    # Конструктор для инициализации объекта узла

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

  

    # Функция для инициализации головы

    def __init__(self):

        self.head = None

  

    # Функция для вставки нового узла в начале

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

  

    # Утилита для печати связанного LinkedList

    def printList(self):

        temp = self.head

        while(temp):

            print temp.data,

            temp = temp.next

  

    def skipMdeleteN(self, M, N):

        curr = self.head

          

        # Основной цикл, который проходит через

        # весь список

        while(curr):

            # Пропустить M узлов

            for count in range(1, M):

                if curr is None:

                    return 

                curr = curr.next

                      

            if curr is None :

                return 

  

            # Начать со следующего узла и удалить N узлов

            t = curr.next 

            for count in range(1, N+1):

                if t is None:

                    break

                t = t.next

      

            # Свяжите предыдущий список с повторными узлами

            curr.next = t

            # Установить текущий указатель для следующей итерации

            curr =

  
# Программа драйвера для проверки вышеуказанной функции

  
# Создать следующий связанный список
# 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9-> 10

llist = LinkedList()

M = 2 

N = 3

llist.push(10)

llist.push(9)

llist.push(8)

llist.push(7)

llist.push(6)

llist.push(5)

llist.push(4)

llist.push(3)

llist.push(2)

llist.push(1)

  

print "M = %d, N = %d\nGiven Linked List is:" %(M, N)

llist.printList()

print 

  
llist.skipMdeleteN(M, N)

  

print "\nLinked list after deletion is"

llist.printList()

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для удаления N узлов
// после M узлов связанного списка

using System;

  

class GFG 

  
// Узел связанного списка

public class Node 

    public int data; 

    public Node next; 

}; 

  
/ * Функция для вставки узла в начале * /

static Node push( Node head_ref, int new_data) 

    / * выделить узел * /

    Node new_node = new Node(); 

  

    / * вставить данные * /

    new_node.data = new_data; 

  

    / * связать старый список с новым узлом * /

    new_node.next = (head_ref); 

  

    / * переместить голову, чтобы указать на новый узел * /

    (head_ref) = new_node; 

      

    return head_ref; 

  
/ * Функция для печати связанного списка * /

static void printList( Node head) 

    Node temp = head; 

    while (temp != null

    

        Console.Write("{0} ", temp.data); 

        temp = temp.next; 

    

    Console.Write("\n"); 

  
// Функция для пропуска M узлов, а затем
// удаляем N узлов связанного списка.

static void skipMdeleteN( Node head, int M, int N) 

    Node curr = head, t; 

    int count; 

  

    // Основной цикл, который проходит

    // через весь список

    while (curr!=null

    

        // Пропустить M узлов

        for (count = 1; count < M && 

                curr != null; count++) 

            curr = curr.next; 

  

        // Если мы достигли конца списка, вернемся

        if (curr == null

            return

  

        // Начать со следующего узла и удалить N узлов

        t = curr.next; 

        for (count = 1; count <= N && t != null; count++) 

        

            Node temp = t; 

            t = t.next; 

        

          

        // Связать предыдущий список с остальными узлами

        curr.next = t; 

  

        // Установить текущий указатель для следующей итерации

        curr = t; 

    

  
// Код драйвера

public static void Main(String []args) 

    / * Создать следующий связанный список

    1.2.3.4.5.6.7.8.9.10 * /

    Node head = null

    int M=2, N=3; 

    head=push(head, 10); 

    head=push(head, 9); 

    head=push(head, 8); 

    head=push(head, 7); 

    head=push(head, 6); 

    head=push(head, 5); 

    head=push(head, 4); 

    head=push(head, 3); 

    head=push(head, 2); 

    head=push(head, 1); 

  

    Console.Write("M = {0}, N = {1} \nGiven"

                        "Linked list is :\n", M, N); 

    printList(head); 

  

    skipMdeleteN(head, M, N); 

  

    Console.Write("\nLinked list after deletion is :\n"); 

    printList(head); 


  
// Этот код предоставлен Rajput-Ji


Выход:

M = 2, N = 3
Given Linked list is :
1 2 3 4 5 6 7 8 9 10

Linked list after deletion is :
1 2 6 7

Сложность времени: O (n), где n — количество узлов в связанном списке.

Эта статья предоставлена Чандрой Пракаш . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Удалить N узлов после M узлов связанного списка

0.00 (0%) 0 votes