Рубрики

Переместить все вхождения элемента в конец связанного списка

При наличии связанного списка и ключа в нем задача состоит в том, чтобы переместить все вхождения данного ключа в конец связанного списка, сохраняя порядок всех остальных элементов одинаковым.

Примеры:

Input  : 1 -> 2 -> 2 -> 4 -> 3
         key = 2 
Output : 1 -> 4 -> 3 -> 2 -> 2

Input  : 6 -> 6 -> 7 -> 6 -> 3 -> 10
         key = 6
Output : 7 -> 3 -> 10 -> 6 -> 6 -> 6

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

Сложность времени: O (n 2 )

Эффективное решение 1: сохранить два указателя:
pCrawl => Указатель для обхода всего списка один за другим.
pKey => Указатель на вхождение ключа, если ключ найден. Остальное так же, как pCrawl.

Мы начинаем оба вышеуказанных указателя с заголовка связанного списка. Мы перемещаем pKey только тогда, когда pKey не указывает на клавишу. Мы всегда перемещаем pCrawl . Таким образом, когда pCrawl и pKey не совпадают, мы должны найти ключ, который находится перед pCrawl , поэтому мы меняем данные pCrawl и pKey и перемещаем pKey в следующее место. Инвариант цикла состоит в том, что после замены данных все элементы от pKey до pCrawl являются ключами.

Ниже приведена реализация этого подхода.

C ++

// C ++ программа для перемещения всех вхождений
// данный ключ до конца.
#include <bits/stdc++.h>

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

struct Node {

    int data;

    struct Node* next;

};

  
// Функция срочности для создания нового узла.

struct Node* newNode(int x)

{

    Node* temp = new Node;

    temp->data = x;

    temp->next = NULL;

}

  
// Сервисная функция для печати элементов
// в связанном списке

void printList(Node* head)

{

    struct Node* temp = head;

    while (temp != NULL) {

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

        temp = temp->next;

    }

    printf("\n");

}

  
// Перемещает все вхождения данного ключа в
// конец связанного списка.

void moveToEnd(Node* head, int key)

{

    // Отслеживает места, где ключ

    // настоящее.

    struct Node* pKey = head;

  

    // Пересечь список

    struct Node* pCrawl = head;

    while (pCrawl != NULL) {

        // Если текущий указатель не совпадает с указателем

        // в ключевое место, то мы должны были найти

        // ключ в связанном списке. Мы меняем данные pCrawl

        // и pKey и перемещаем pKey в следующую позицию.

        if (pCrawl != pKey && pCrawl->data != key) {

            pKey->data = pCrawl->data;

            pCrawl->data = key;

            pKey = pKey->next;

        }

  

        // Найти следующую позицию, где присутствует ключ

        if (pKey->data != key)

            pKey = pKey->next;

  

        // Переходим к следующему узлу

        pCrawl = pCrawl->next;

    }

}

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

int main()

{

    Node* head = newNode(10);

    head->next = newNode(20);

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

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

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

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

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

  

    printf("Before moveToEnd(), the Linked list is\n");

    printList(head);

  

    int key = 10;

    moveToEnd(head, key);

  

    printf("\nAfter moveToEnd(), the Linked list is\n");

    printList(head);

  

    return 0;

}

Джава

// Java-программа для перемещения всех вхождений
// данный ключ до конца.

class GFG {

  

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

    static class Node {

        int data;

        Node next;

    }

  

    // Функция срочности для создания нового узла.

    static Node newNode(int x)

    {

        Node temp = new Node();

        temp.data = x;

        temp.next = null;

        return temp;

    }

  

    // Сервисная функция для печати элементов

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

    static void printList(Node head)

    {

        Node temp = head;

        while (temp != null) {

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

            temp = temp.next;

        }

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

    }

  

    // Перемещает все вхождения данного ключа в

    // конец связанного списка.

    static void moveToEnd(Node head, int key)

    {

        // Отслеживает места, где ключ

        // настоящее.

        Node pKey = head;

  

        // Пересечь список

        Node pCrawl = head;

        while (pCrawl != null) {

            // Если текущий указатель не совпадает с указателем

            // в ключевое место, то мы должны были найти

            // ключ в связанном списке. Мы меняем данные pCrawl

            // и pKey и перемещаем pKey в следующую позицию.

            if (pCrawl != pKey && pCrawl.data != key) {

                pKey.data = pCrawl.data;

                pCrawl.data = key;

                pKey = pKey.next;

            }

  

            // Найти следующую позицию, где присутствует ключ

            if (pKey.data != key)

                pKey = pKey.next;

  

            // Переходим к следующему узлу

            pCrawl = pCrawl.next;

        }

    }

  

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

    public static void main(String args[])

    {

        Node head = newNode(10);

        head.next = newNode(20);

        head.next.next = newNode(10);

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

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

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

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

  

        System.out.printf("Before moveToEnd(), the Linked list is\n");

        printList(head);

  

        int key = 10;

        moveToEnd(head, key);

  

        System.out.printf("\nAfter moveToEnd(), the Linked list is\n");

        printList(head);

    }

}

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

C #

// C # программа для перемещения всех вхождений
// данный ключ до конца.

using System;

  

class GFG {

  

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

    public class Node {

        public int data;

        public Node next;

    }

  

    // Функция срочности для создания нового узла.

    static Node newNode(int x)

    {

        Node temp = new Node();

        temp.data = x;

        temp.next = null;

        return temp;

    }

  

    // Сервисная функция для печати элементов

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

    static void printList(Node head)

    {

        Node temp = head;

        while (temp != null) {

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

            temp = temp.next;

        }

        Console.Write("\n");

    }

  

    // Перемещает все вхождения данного ключа в

    // конец связанного списка.

    static void moveToEnd(Node head, int key)

    {

        // Отслеживает места, где ключ

        // настоящее.

        Node pKey = head;

  

        // Пересечь список

        Node pCrawl = head;

        while (pCrawl != null) {

            // Если текущий указатель не совпадает с указателем

            // в ключевое место, то мы должны были найти

            // ключ в связанном списке. Мы меняем данные pCrawl

            // и pKey и перемещаем pKey в следующую позицию.

            if (pCrawl != pKey && pCrawl.data != key) {

                pKey.data = pCrawl.data;

                pCrawl.data = key;

                pKey = pKey.next;

            }

  

            // Найти следующую позицию, где присутствует ключ

            if (pKey.data != key)

                pKey = pKey.next;

  

            // Переходим к следующему узлу

            pCrawl = pCrawl.next;

        }

    }

  

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

    public static void Main(String[] args)

    {

        Node head = newNode(10);

        head.next = newNode(20);

        head.next.next = newNode(10);

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

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

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

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

  

        Console.Write("Before moveToEnd(), the Linked list is\n");

        printList(head);

  

        int key = 10;

        moveToEnd(head, key);

  

        Console.Write("\nAfter moveToEnd(), the Linked list is\n");

        printList(head);

    }

}

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


Выход:

Before moveToEnd(), the Linked list is
10 20 10 30 40 10 60 

After moveToEnd(), the Linked list is
20 30 40 60 10 10 10 

Сложность времени: O (n) требует только одного обхода списка.

Эффективное решение 2:
1. Пройдите по связанному списку и возьмите указатель на хвост.
2. Теперь проверьте ключ и данные узла->, если они равны, переместите узел на последнюю-следующую, иначе переместите
вперед.

Джава

// Java-код для удаления ключевого элемента до конца связанного списка

import java.util.*;

  
// Класс узла

class Node {

    int data;

    Node next;

  

    public Node(int data)

    {

        this.data = data;

        this.next = null;

    }

}

  

class gfg {

  

    static Node root;

  

    // Функция для удаления ключа до конца

    public static Node keyToEnd(Node head, int key)

    {

  

        // Узел продолжать указывать на хвост

        Node tail = head;

  

        if (head == null) {

            return null;

        }

  

        while (tail.next != null) {

            tail = tail.next;

        }

  

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

        Node last = tail;

  

        Node current = head;

        Node prev = null;

  

        // Узел prev2 указывает на предыдущий, когда head.data! = Key

        Node prev2 = null;

  

        // цикл для выполнения операций по удалению ключа до конца

        while (current != tail) {

            if (current.data == key && prev2 == null) {

                prev = current;

                current = current.next;

                head = current;

                last.next = prev;

                last = last.next;

                last.next = null;

                prev = null;

            }

            else {

                if (current.data == key && prev2 != null) {

                    prev = current;

                    current = current.next;

                    prev2.next = current;

                    last.next = prev;

                    last = last.next;

                    last.next = null;

                }

                else if (current != tail) {

                    prev2 = current;

                    current = current.next;

                }

            }

        }

        return head;

    }

  

    // Функция для отображения связанного списка

    public static void display(Node root)

    {

        while (root != null) {

            System.out.print(root.data + " ");

            root = root.next;

        }

    }

  

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

    public static void main(String args[])

    {

        root = new Node(5);

        root.next = new Node(2);

        root.next.next = new Node(2);

        root.next.next.next = new Node(7);

        root.next.next.next.next = new Node(2);

        root.next.next.next.next.next = new Node(2);

        root.next.next.next.next.next.next = new Node(2);

  

        int key = 2;

        System.out.println("Linked List before operations :");

        display(root);

        System.out.println("\nLinked List after operations :");

        root = keyToEnd(root, key);

        display(root);

    }

}

C #

// C # код для удаления ключа
// элемент в конец связанного списка

using System;

  
// Класс узла

public class Node {

    public int data;

    public Node next;

  

    public Node(int data)

    {

        this.data = data;

        this.next = null;

    }

}

  

class GFG {

  

    static Node root;

  

    // Функция для удаления ключа до конца

    public static Node keyToEnd(Node head, int key)

    {

  

        // Узел продолжать указывать на хвост

        Node tail = head;

  

        if (head == null) {

            return null;

        }

  

        while (tail.next != null) {

            tail = tail.next;

        }

  

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

        Node last = tail;

  

        Node current = head;

        Node prev = null;

  

        // Узел prev2 указывает на

        // предыдущий когда head.data! = key

        Node prev2 = null;

  

        // цикл для выполнения операций

        // удалить ключ до конца

        while (current != tail) {

            if (current.data == key && prev2 == null) {

                prev = current;

                current = current.next;

                head = current;

                last.next = prev;

                last = last.next;

                last.next = null;

                prev = null;

            }

            else {

                if (current.data == key && prev2 != null) {

                    prev = current;

                    current = current.next;

                    prev2.next = current;

                    last.next = prev;

                    last = last.next;

                    last.next = null;

                }

                else if (current != tail) {

                    prev2 = current;

                    current = current.next;

                }

            }

        }

        return head;

    }

  

    // Функция для отображения связанного списка

    public static void display(Node root)

    {

        while (root != null) {

            Console.Write(root.data + " ");

            root = root.next;

        }

    }

  

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

    public static void Main()

    {

        root = new Node(5);

        root.next = new Node(2);

        root.next.next = new Node(2);

        root.next.next.next = new Node(7);

        root.next.next.next.next = new Node(2);

        root.next.next.next.next.next = new Node(2);

        root.next.next.next.next.next.next = new Node(2);

  

        int key = 2;

        Console.WriteLine("Linked List before operations :");

        display(root);

        Console.WriteLine("\nLinked List after operations :");

        root = keyToEnd(root, key);

        display(root);

    }

}

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


Выход:

Linked List before operations :
5 2 2 7 2 2 2 
Linked List after operations :
5 7 2 2 2 2 2 

Спасибо Равиндеру Кумару за то, что он предложил этот метод.

Эффективное решение 3: вести отдельный список ключей. Мы инициализируем этот список ключей как пустой. Мы пересекаем данный список. Для каждого найденного ключа мы удаляем его из исходного списка и вставляем в отдельный список ключей. Наконец, мы связываем список ключей в конце оставшегося списка. Временная сложность этого решения также равна O (n), и для этого также требуется только один обход списка.

Эта статья предоставлена МАЖАР ИМАМ ХАН. Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Переместить все вхождения элемента в конец связанного списка

0.00 (0%) 0 votes