Рубрики

Разделение связанного списка вокруг заданного значения и сохранение первоначального порядка

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

Примеры:

Input : 1->4->3->2->5->2->3, 
        x = 3
Output: 1->2->2->3->3->4->5

Input : 1->4->2->10 
        x = 3
Output: 1->2->4->10

Input : 10->4->20->10->3 
        x = 3
Output: 3->10->4->20->10 

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

Ниже приведен алгоритм решения этой проблемы:

  • Инициализируйте первый и последний узлы ниже трех связанных списков как NULL.
    1. Связанный список значений меньше х.
    2. Связанный список значений равен x.
    3. Связанный список значений больше х.
  • Теперь переберите исходный связанный список. Если значение узла меньше x, тогда добавьте его в конец меньшего списка. Если значение равно x, то в конце равного списка. А если значение больше, то в конце большего списка.
  • Теперь объедините три списка.

Ниже приведена реализация вышеуказанной идеи.

C ++

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

using namespace std;

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

struct Node

{

    int data;

    struct Node* next;

};

  
// Вспомогательная функция для создания нового узла

Node *newNode(int data)

{

    struct Node* new_node = new Node;

    new_node->data  = data;

    new_node->next = NULL;

    return new_node;

}

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

struct Node *partition(struct Node *head, int x)

{

    / * Давайте инициализируем первый и последний узлы

      три связанных списка

        1) Связанный список значений меньше х.

        2) Связанный список значений равен x.

        3) Связанный список значений больше, чем х. * /

    struct Node *smallerHead = NULL, *smallerLast = NULL;

    struct Node *greaterLast = NULL, *greaterHead = NULL;

    struct Node *equalHead = NULL, *equalLast = NULL;

  

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

    // соответствующих связанных списков.

    while (head != NULL)

    {

        // Если текущий узел равен x, добавить его

        // к списку значений х

        if (head->data == x)

        {

            if (equalHead == NULL)

                equalHead = equalLast = head;

            else

            {

                equalLast->next = head;

                equalLast = equalLast->next;

            }

        }

  

        // Если текущий узел меньше X, добавляем

        // это к списку меньших значений

        else if (head->data < x)

        {

            if (smallerHead == NULL)

                smallerLast = smallerHead = head;

            else

            {

                smallerLast->next = head;

                smallerLast = head;

            }

        }

        else // Добавить в список больших значений

        {

            if (greaterHead == NULL)

                greaterLast = greaterHead = head;

            else

            {

                greaterLast->next  = head;

                greaterLast = head;

            }

        }

  

        head = head->next;

    }

  

    // Исправить конец большего связанного списка в NULL, если это

    // список имеет несколько узлов

    if (greaterLast != NULL)

        greaterLast->next = NULL;

  

    // Соединяем три списка

  

    // Если меньший список пуст

    if (smallerHead == NULL)

    {

        if (equalHead == NULL)

            return greaterHead;

        equalLast->next = greaterHead;

        return equalHead;

    }

  

    // Если меньший список не пуст

    // и равный список пуст

    if (equalHead == NULL)

    {

        smallerLast->next = greaterHead;

        return smallerHead;

    }

  

    // Если список меньше и равен

    // не пустые

    smallerLast->next = equalHead;

    equalLast->next = greaterHead;

    return  smallerHead;

}

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

void printList(struct Node *head)

{

    struct Node *temp = head;

    while (temp != NULL)

    {

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

        temp = temp->next;

    }

}

  
// Драйвер программы для запуска дела

int main()

{

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

    struct Node* head = newNode(10);

    head->next = newNode(4);

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

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

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

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

  

    int x = 3;

    head = partition(head, x);

    printList(head);

    return 0;

}

Джава

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

class GfG 

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

static class Node 

    int data; 

    Node next; 

}

  
// Вспомогательная функция для создания нового узла

static Node newNode(int data) 

    Node new_node = new Node(); 

    new_node.data = data; 

    new_node.next = null

    return new_node; 

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

static Node partition(Node head, int x) 

      

    / * Давайте инициализируем первый и последний узлы

    три связанных списка

        1) Связанный список значений меньше х.

        2) Связанный список значений равен x.

        3) Связанный список значений больше, чем х. * /

    Node smallerHead = null, smallerLast = null

    Node greaterLast = null, greaterHead = null

    Node equalHead = null, equalLast =null

  

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

    // соответствующих связанных списков.

    while (head != null

    

        // Если текущий узел равен x, добавить его

        // к списку значений х

        if (head.data == x) 

        

            if (equalHead == null

                equalHead = equalLast = head; 

            else

            

                equalLast.next = head; 

                equalLast = equalLast.next; 

            

        

  

        // Если текущий узел меньше X, добавляем

        // это к списку меньших значений

        else if (head.data < x) 

        

            if (smallerHead == null

                smallerLast = smallerHead = head; 

            else

            

                smallerLast.next = head; 

                smallerLast = head; 

            

        

        else // Добавить в список больших значений

        

            if (greaterHead == null

                greaterLast = greaterHead = head; 

            else

            

                greaterLast.next = head; 

                greaterLast = head; 

            

        

        head = head.next; 

    

  

    // Исправить конец большего связанного списка в NULL, если это

    // список имеет несколько узлов

    if (greaterLast != null

        greaterLast.next = null

  

    // Соединяем три списка

  

    // Если меньший список пуст

    if (smallerHead == null

    

        if (equalHead == null

            return greaterHead; 

        equalLast.next = greaterHead; 

        return equalHead; 

    

  

    // Если меньший список не пуст

    // и равный список пуст

    if (equalHead == null

    

        smallerLast.next = greaterHead; 

        return smallerHead; 

    

  

    // Если список меньше и равен

    // не пустые

    smallerLast.next = equalHead; 

    equalLast.next = greaterHead; 

    return smallerHead; 

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

static void printList(Node head) 

    Node temp = head; 

    while (temp != null

    

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

        temp = temp.next; 

    

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

public static void main(String[] args) 

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

    Node head = newNode(10); 

    head.next = newNode(4); 

    head.next.next = newNode(5); 

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

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

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

  

    int x = 3

    head = partition(head, x); 

    printList(head); 

}

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

C #

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

using System;

  

public class GfG 

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

public class Node 

    public int data; 

    public Node next; 

}

  
// Вспомогательная функция для создания нового узла

static Node newNode(int data) 

    Node new_node = new Node(); 

    new_node.data = data; 

    new_node.next = null

    return new_node; 

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

static Node partition(Node head, int x) 

      

    / * Давайте инициализируем первый и последний узлы

    три связанных списка

        1) Связанный список значений меньше х.

        2) Связанный список значений равен x.

        3) Связанный список значений больше, чем х. * /

    Node smallerHead = null, smallerLast = null

    Node greaterLast = null, greaterHead = null

    Node equalHead = null, equalLast =null

  

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

    // соответствующих связанных списков.

    while (head != null

    

        // Если текущий узел равен x, добавить его

        // к списку значений х

        if (head.data == x) 

        

            if (equalHead == null

                equalHead = equalLast = head; 

            else

            

                equalLast.next = head; 

                equalLast = equalLast.next; 

            

        

  

        // Если текущий узел меньше X, добавляем

        // это к списку меньших значений

        else if (head.data < x) 

        

            if (smallerHead == null

                smallerLast = smallerHead = head; 

            else

            

                smallerLast.next = head; 

                smallerLast = head; 

            

        

        else // Добавить в список больших значений

        

            if (greaterHead == null

                greaterLast = greaterHead = head; 

            else

            

                greaterLast.next = head; 

                greaterLast = head; 

            

        

        head = head.next; 

    

  

    // Исправить конец большего связанного списка в NULL, если это

    // список имеет несколько узлов

    if (greaterLast != null

        greaterLast.next = null

  

    // Соединяем три списка

  

    // Если меньший список пуст

    if (smallerHead == null

    

        if (equalHead == null

            return greaterHead; 

        equalLast.next = greaterHead; 

        return equalHead; 

    

  

    // Если меньший список не пуст

    // и равный список пуст

    if (equalHead == null

    

        smallerLast.next = greaterHead; 

        return smallerHead; 

    

  

    // Если список меньше и равен

    // не пустые

    smallerLast.next = equalHead; 

    equalLast.next = greaterHead; 

    return smallerHead; 

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

static void printList(Node head) 

    Node temp = head; 

    while (temp != null

    

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

        temp = temp.next; 

    

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

public static void Main() 

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

    Node head = newNode(10); 

    head.next = newNode(4); 

    head.next.next = newNode(5); 

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

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

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

  

    int x = 3; 

    head = partition(head, x); 

    printList(head); 

}
}

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


Выход:

2 10 4 5 30 50

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

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

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

Разделение связанного списка вокруг заданного значения и сохранение первоначального порядка

0.00 (0%) 0 votes