Рубрики

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

Если указан односвязный список, удалите середину связанного списка. Например, если данный связанный список 1-> 2-> 3-> 4-> 5, то связанный список должен быть изменен на 1-> 2-> 4-> 5

Если есть даже узлы, то будет два средних узла, нам нужно удалить второй средний элемент. Например, если данный связанный список имеет вид 1-> 2-> 3-> 4-> 5-> 6, его следует изменить на 1-> 2-> 3-> 5-> 6.

Если входной связанный список имеет значение NULL, то он должен оставаться NULL.

Если входной связанный список имеет 1 узел, то этот узел должен быть удален, а новый заголовок должен быть возвращен.

Простое решение — сначала подсчитать количество узлов в связанном списке, а затем удалить n / 2-й узел, используя простой процесс удаления.

Приведенное выше решение требует двух обходов связанного списка. Мы можем удалить средний узел, используя один обход. Идея состоит в том, чтобы использовать два указателя, slow_ptr и fast_ptr. Оба указателя начинаются с заголовка списка. Когда fast_ptr достигает конца, slow_ptr достигает середины. Эта идея такая же, как и в методе 2 этого поста. Дополнительная вещь в этом посте — отслеживать предыдущее среднее, чтобы мы могли удалить среднее.

Ниже приведена реализация.

C ++

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

using namespace std;

  
/ * Узел списка ссылок * /

struct Node

{

    int data;

    struct Node* next;

};

  
// Удаляет средний узел и возвращает заголовок
// модифицированный список

struct Node* deleteMid(struct Node *head)

{

    // Базовые случаи

    if (head == NULL)

        return NULL;

    if (head->next == NULL)

    {

        delete head;

        return NULL;

    }

  

    // Инициализируем медленные и быстрые указатели для достижения

    // середина связанного списка

    struct Node *slow_ptr = head;

    struct Node *fast_ptr = head;

  

    // Найти середину и предыдущую середины.

    struct Node *prev; // Для сохранения предыдущего из slow_ptr

    while (fast_ptr != NULL && fast_ptr->next != NULL)

    {

        fast_ptr = fast_ptr->next->next;

        prev = slow_ptr;

        slow_ptr = slow_ptr->next;

    }

  

    // Удалить средний узел

    prev->next = slow_ptr->next;

    delete slow_ptr;

  

    return head;

}

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

void printList(struct Node *ptr)

{

    while (ptr != NULL)

    {

        cout << ptr->data << "->";

        ptr = ptr->next;

    }

    cout << "NULL\n";

}

  
// Сервисная функция для создания нового узла.

Node *newNode(int data)

{

    struct Node *temp = new Node;

    temp->data = data;

    temp->next = NULL;

    return temp;

}

  
/ * Сушилка для проверки вышеуказанной функции * /

int main()

{

    / * Начнем с пустого списка * /

    struct Node* head = newNode(1);

    head->next = newNode(2);

    head->next->next = newNode(3);

    head->next->next->next = newNode(4);

  

    cout << "Gven Linked List\n";

    printList(head);

  

    head = deleteMid(head);

  

    cout << "Linked List after deletion of middle\n";

    printList(head);

  

    return 0;

}

Джава

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

class GfG 

  
/ * Узел списка ссылок * /

static class Node 

    int data; 

    Node next; 

}

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

static Node deleteMid(Node head) 

    // Базовые случаи

    if (head == null

        return null

    if (head.next == null

    

        return null

    

  

    // Инициализируем медленные и быстрые указатели для достижения

    // середина связанного списка

    Node slow_ptr = head; 

    Node fast_ptr = head; 

  

    // Найти середину и предыдущую середины.

    Node prev = null

      

    // Для сохранения предыдущего из slow_ptr

    while (fast_ptr != null && fast_ptr.next != null

    

        fast_ptr = fast_ptr.next.next; 

        prev = slow_ptr; 

        slow_ptr = slow_ptr.next; 

    

  

    // Удалить средний узел

    prev.next = slow_ptr.next; 

  

    return head; 

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

static void printList(Node ptr) 

    while (ptr != null

    

        System.out.print(ptr.data + "->"); 

        ptr = ptr.next; 

    

    System.out.println("NULL"); 

  
// Сервисная функция для создания нового узла.

static Node newNode(int data) 

    Node temp = new Node(); 

    temp.data = data; 

    temp.next = null

    return temp; 

  
/ * Сушильный код * /

public static void main(String[] args) 

    / * Начнем с пустого списка * /

    Node head = newNode(1); 

    head.next = newNode(2); 

    head.next.next = newNode(3); 

    head.next.next.next = newNode(4); 

  

    System.out.println("Gven Linked List"); 

    printList(head); 

  

    head = deleteMid(head); 

  

    System.out.println("Linked List after deletion of middle"); 

    printList(head); 

}

  
// Этот код предоставлен Prerna saini.

C #

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

using System;

      

class GfG 

  

    / * Узел списка ссылок * /

    class Node 

    

        public int data; 

        public Node next; 

    }

  

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

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

    static Node deleteMid(Node head) 

    

        // Базовые случаи

        if (head == null

            return null

        if (head.next == null

        

            return null

        

  

        // Инициализируем медленные и быстрые указатели

        // достичь середины связанного списка

        Node slow_ptr = head; 

        Node fast_ptr = head; 

  

        // Найти середину и предыдущую середины.

        Node prev = null

  

        // Для сохранения предыдущего из slow_ptr

        while (fast_ptr != null && 

                fast_ptr.next != null

        

            fast_ptr = fast_ptr.next.next; 

            prev = slow_ptr; 

            slow_ptr = slow_ptr.next; 

        

  

        // Удалить средний узел

        prev.next = slow_ptr.next; 

  

        return head; 

    

  

    // Утилита для печати

    // данный связанный список

    static void printList(Node ptr) 

    

        while (ptr != null

        

            Console.Write(ptr.data + "->"); 

            ptr = ptr.next; 

        

        Console.WriteLine("NULL"); 

    

  

    // Сервисная функция для создания нового узла.

    static Node newNode(int data) 

    

        Node temp = new Node(); 

        temp.data = data; 

        temp.next = null

        return temp; 

    

  

    / * Сушильный код * /

    public static void Main(String[] args) 

    

        / * Начнем с пустого списка * /

        Node head = newNode(1); 

        head.next = newNode(2); 

        head.next.next = newNode(3); 

        head.next.next.next = newNode(4); 

  

        Console.WriteLine("Gven Linked List"); 

        printList(head); 

  

        head = deleteMid(head); 

  

        Console.WriteLine("Linked List after"

                            "deletion of middle"); 

        printList(head); 

    }

}

  
/ * Этот код предоставлен 29AjayKumar * /


Выход :

Gven Linked List
1->2->3->4->NULL
Linked List after deletion of middle
1->2->4->NULL

Эта статья предоставлена Пиюшем Гуптой . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

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

0.00 (0%) 0 votes