Рубрики

Рекурсивный выбор сортировки для односвязного списка | Обмен ссылками узла

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

Примеры:

Input : 10 -> 12 -> 8 -> 4 -> 6
Output : 4 -> 6 -> 8 -> 10 -> 12

В Selection Sort мы сначала находим минимальный элемент, меняем его местами с начального узла и повторяем для оставшегося списка. Ниже приведена рекурсивная реализация этих шагов для связанного списка.

recurSelectionSort(head)
     if head->next == NULL
         return head
     Initialize min = head
     Initialize beforeMin = NULL
     Initialize ptr = head
    
     while ptr->next != NULL 
         if min->data > ptr->next->data
         min = ptr->next
         beforeMin = ptr
     ptr = ptr->next    
    
     if min != head
         swapNodes(&head, head, min, beforeMin)
    
     head->next = recurSelectionSort(head->next)
     return head

swapNodes(head_ref, currX, currY, prevY)
     head_ref = currY
     prevY->next = currX

     Initialize temp = currY->next
     currY->next = currX->next
     currX->next  = temp    

SwapNodes (head_ref, currX, currY, prevY) основан на подходе, обсуждаемом здесь, но он соответствующим образом модифицирован для реализации этого поста.

C ++

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

using namespace std;

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

struct Node {

    int data;

    struct Node* next;

};

  
// функция для замены узлов 'currX' и 'currY' в
// связанный список без обмена данными

void swapNodes(struct Node** head_ref, struct Node* currX,

               struct Node* currY, struct Node* prevY)

{

    // сделать 'currY' новой головой

    *head_ref = currY;

  

    // настроить ссылки

    prevY->next = currX;

  

    // Поменять местами следующие указатели

    struct Node* temp = currY->next;

    currY->next = currX->next;

    currX->next = temp;

}

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

struct Node* recurSelectionSort(struct Node* head)

{

    // если есть только один узел

    if (head->next == NULL)

        return head;

  

    // 'min' - указатель для хранения узла, имеющего

    // минимальное значение данных

    struct Node* min = head;

  

    // 'beforeMin' - указатель на предыдущий узел хранилища

    // к узлу 'min'

    struct Node* beforeMin = NULL;

    struct Node* ptr;

  

    // пройти список до последнего узла

    for (ptr = head; ptr->next != NULL; ptr = ptr->next) {

  

        // если true, тогда обновляем 'min' и 'beforeMin'

        if (ptr->next->data < min->data) {

            min = ptr->next;

            beforeMin = ptr;

        }

    }

  

    // если min и head не совпадают,

    // меняем головной узел с узлом 'min'

    if (min != head)

        swapNodes(&head, head, min, beforeMin);

  

    // рекурсивно сортируем оставшийся список

    head->next = recurSelectionSort(head->next);

  

    return head;

}

  
// функция для сортировки заданного связанного списка

void sort(struct Node** head_ref)

{

    // если список пуст

    if ((*head_ref) == NULL)

        return;

  

    // сортируем список с помощью рекурсивного выбора

    // метод сортировки

    *head_ref = recurSelectionSort(*head_ref);

}

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

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)

{

    while (head != NULL) {

        cout << head->data << " ";

        head = head->next;

    }

}

  
// Программа драйвера для тестирования выше

int main()

{

    struct Node* head = NULL;

  

    // создаем связанный список 10-> 12-> 8-> 4-> 6

    push(&head, 6);

    push(&head, 4);

    push(&head, 8);

    push(&head, 12);

    push(&head, 10);

  

    cout << "Linked list before sorting:n";

    printList(head);

  

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

    sort(&head);

  

    cout << "\nLinked list after sorting:n";

    printList(head);

  

    return 0;

}

Джава

// Реализация рекурсивной сортировки на Java
// для односвязного списка | Обмен ссылками узла

class GFG

{

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

static class Node

    int data; 

    Node next; 

}; 

  
// функция для замены узлов 'currX' и 'currY' в
// связанный список без обмена данными

static Node swapNodes( Node head_ref, Node currX, 

                        Node currY, Node prevY) 

    // сделать 'currY' новой головой

    head_ref = currY; 

  

    // настроить ссылки

    prevY.next = currX; 

  

    // Поменять местами следующие указатели

    Node temp = currY.next; 

    currY.next = currX.next; 

    currX.next = temp; 

    return head_ref;

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

static Node recurSelectionSort( Node head) 

    // если есть только один узел

    if (head.next == null

        return head; 

  

    // 'min' - указатель для хранения узла, имеющего

    // минимальное значение данных

    Node min = head; 

  

    // 'beforeMin' - указатель на предыдущий узел хранилища

    // к узлу 'min'

    Node beforeMin = null

    Node ptr; 

  

    // пройти список до последнего узла

    for (ptr = head; ptr.next != null; ptr = ptr.next) 

    

  

        // если true, тогда обновляем 'min' и 'beforeMin'

        if (ptr.next.data < min.data) 

        

            min = ptr.next; 

            beforeMin = ptr; 

        

    

  

    // если min и head не совпадают,

    // меняем головной узел с узлом 'min'

    if (min != head) 

        head = swapNodes(head, head, min, beforeMin); 

  

    // рекурсивно сортируем оставшийся список

    head.next = recurSelectionSort(head.next); 

  

    return head; 

  
// функция для сортировки заданного связанного списка

static Node sort( Node head_ref) 

    // если список пуст

    if ((head_ref) == null

        return null

  

    // сортируем список с помощью рекурсивного выбора

    // метод сортировки

    head_ref = recurSelectionSort(head_ref); 

    return head_ref;

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

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) 

    while (head != null

    

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

        head = head.next; 

    

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

public static void main(String args[])

    Node head = null

  

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

    head = push(head, 6); 

    head = push(head, 4); 

    head = push(head, 8); 

    head = push(head, 12); 

    head = push(head, 10); 

  

    System.out.println( "Linked list before sorting:"); 

    printList(head); 

  

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

    head = sort(head); 

  

    System.out.print( "\nLinked list after sorting:"); 

    printList(head); 


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

C #

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

using System;

public class GFG

{

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

public class Node

    public int data; 

    public Node next; 

}; 

  
// функция для замены узлов 'currX' и 'currY' в
// связанный список без обмена данными

static Node swapNodes(Node head_ref, Node currX, 

                      Node currY, Node prevY) 

    // сделать 'currY' новой головой

    head_ref = currY; 

  

    // настроить ссылки

    prevY.next = currX; 

  

    // Поменять местами следующие указатели

    Node temp = currY.next; 

    currY.next = currX.next; 

    currX.next = temp; 

    return head_ref;

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

static Node recurSelectionSort(Node head) 

    // если есть только один узел

    if (head.next == null

        return head; 

  

    // 'min' - указатель для хранения узла, имеющего

    // минимальное значение данных

    Node min = head; 

  

    // 'beforeMin' - указатель на узел хранилища

    // перед узлом 'min'

    Node beforeMin = null

    Node ptr; 

  

    // пройти список до последнего узла

    for (ptr = head; ptr.next != null

                     ptr = ptr.next) 

    

  

        // если true, тогда обновляем 'min' и 'beforeMin'

        if (ptr.next.data < min.data) 

        

            min = ptr.next; 

            beforeMin = ptr; 

        

    

  

    // если min и head не совпадают,

    // меняем головной узел с узлом 'min'

    if (min != head) 

        head = swapNodes(head, head, min, beforeMin); 

  

    // рекурсивно сортируем оставшийся список

    head.next = recurSelectionSort(head.next); 

  

    return head; 

  
// функция для сортировки заданного связанного списка

static Node sort( Node head_ref) 

    // если список пуст

    if ((head_ref) == null

        return null

  

    // сортируем список с помощью рекурсивного выбора

    // метод сортировки

    head_ref = recurSelectionSort(head_ref); 

    return head_ref;

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

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) 

    while (head != null

    

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

        head = head.next; 

    

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

public static void Main(String []args)

    Node head = null

  

    // создаем связанный список 10-> 12-> 8-> 4-> 6

    head = push(head, 6); 

    head = push(head, 4); 

    head = push(head, 8); 

    head = push(head, 12); 

    head = push(head, 10); 

  

    Console.WriteLine("Linked list before sorting:"); 

    printList(head); 

  

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

    head = sort(head); 

  

    Console.Write("\nLinked list after sorting:"); 

    printList(head); 


  

  
// Этот код предоставлен Принчи Сингхом


Выход:

Linked list before sorting:
10 12 8 4 6
Linked list after sorting:
4 6 8 10 12

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

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

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

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

Рекурсивный выбор сортировки для односвязного списка | Обмен ссылками узла

0.00 (0%) 0 votes