Рубрики

Перегруппировать связанный список в зигзагообразном стиле

Для связанного списка переставьте его так, чтобы преобразованный список имел форму a <b> c <d> e <f .., где a, b, c .. — последовательный узел данных связанного списка.

Примеры :

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

Input:  11->15->20->5->10
Output: 11->20->5->15->10

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Простой способ сделать это — отсортировать связанный список с помощью сортировки слиянием, а затем поменять местами альтернативу, но это требует O (n Log n) временной сложности. Здесь n — количество элементов в связанном списке.

Эффективный подход, который требует времени O (n), заключается в использовании одного сканирования, подобного сортировке по пузырькам, и последующем поддержании флага для представления того, какой у нас порядок (). Если текущие два элемента не в этом порядке, то поменять местами эти элементы иначе. Пожалуйста, обратитесь к этому для подробного объяснения порядка обмена.

C ++

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

using namespace std;

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

struct Node

{

    int data;

    struct Node* next;

};

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

void zigZagList(Node *head)

{

    // Если флаг равен true, то следующий узел должен быть больше

    // в желаемом выходе.

    bool flag = true;

  

    // Переходим связанный список, начиная с заголовка.

    Node* current = head;

    while (current->next != NULL)

    {

        if (flag)  / * "<" ожидаемое отношение * /

        {

            / * Если у нас такая ситуация, как A> B> C

               где A, B и C являются последовательными узлами

               в списке мы получаем A> B <C путем замены B

               и С * /

            if (current->data > current->next->data)

                swap(current->data, current->next->data);

        }

        else / * ">" ожидаемое отношение * /

        {

            / * Если у нас такая ситуация, как A <B <C, где

               A, B и C являются последовательными узлами в списке, который мы

               получить A <C> B, поменяв местами B и C * /

            if (current->data < current->next->data)

                swap(current->data, current->next->data);

        }

  

        current = current->next;

        flag = !flag;  / * флаг для обратной проверки * /

    }

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для подталкивания узла * /

void push(Node** head_ref, int new_data)

{

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

    struct Node* new_Node = new Node;

  

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

    new_Node->data  = new_data;

  

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

    new_Node->next = (*head_ref);

  

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

    (*head_ref)    = new_Node;

}

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

void printList(struct Node *Node)

{

    while (Node != NULL)

    {

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

        Node = Node->next;

    }

    printf("NULL");

}

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

int main(void)

{

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

    struct Node* head = NULL;

  

    // создаем список 4 -> 3 -> 7 -> 8 -> 6 -> 2 -> 1

    // ответ должен быть -> 3 7 4 8 2 6 1

    push(&head, 1);

    push(&head, 2);

    push(&head, 6);

    push(&head, 8);

    push(&head, 7);

    push(&head, 3);

    push(&head, 4);

  

    printf("Given linked list \n");

    printList(head);

  

    zigZagList(head);

  

    printf("\nZig Zag Linked list \n");

    printList(head);

  

    return (0);

}

Джава

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

class GfG

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

static class Node 

    int data; 

    Node next; 

}

static Node head = null;

static int temp = 0;

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

static void zigZagList(Node head) 

    // Если флаг равен true, то

    // следующий узел должен быть больше

    // в желаемом выходе.

    boolean flag = true

  

    // Переходим связанный список, начиная с заголовка.

    Node current = head; 

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

    

        if (flag == true) / * "<" ожидаемое отношение * /

        

            / * Если у нас такая ситуация, как A> B> C

            где A, B и C являются последовательными узлами

            в списке мы получаем A> B <C путем замены B

            и С * /

            if (current.data > current.next.data) 

            {

                    temp = current.data;

                    current.data = current.next.data;

                    current.next.data = temp;

            

        

        else / * ">" ожидаемое отношение * /

        

            / * Если у нас такая ситуация, как A <B <C, где

            A, B и C являются последовательными узлами в списке, который мы

            получить A <C> B, поменяв местами B и C * /

            if (current.data < current.next.data) 

            {

                temp = current.data;

                current.data = current.next.data;

                current.next.data = temp;

            

        

  

        current = current.next; 

          

        / * флаг для обратной проверки * /

        flag = !(flag); 

    

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для подталкивания узла * /

static void push( int new_data) 

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

    Node new_Node = new Node(); 

  

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

    new_Node.data = new_data; 

  

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

    new_Node.next = (head); 

  

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

    (head) = new_Node; 

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

static void printList(Node Node) 

    while (Node != null

    

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

        Node = Node.next; 

    

    System.out.println("NULL"); 

  
/ * Код водителя * /

public static void main(String[] args) 

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

    // Node head = null;

  

    // создаем список 4 -> 3 -> 7 -> 8 -> 6 -> 2 -> 1

    // ответ должен быть -> 3 7 4 8 2 6 1

    push(1); 

    push(2); 

    push(6); 

    push(8); 

    push( 7); 

    push( 3); 

    push( 4); 

  

    System.out.println("Given linked list "); 

    printList(head); 

  

    zigZagList(head); 

  

    System.out.println("Zig Zag Linked list "); 

    printList(head); 

}

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

C #

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

using System;

  

class GfG 

  

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

    class Node 

    

        public int data; 

        public Node next; 

    

    static Node head = null

    static int temp = 0; 

  

    // Эта функция распределяет

    // Узел зигзагообразным способом

    static void zigZagList(Node head) 

    

        // Если флаг равен true, то

        // следующий узел должен быть больше

        // в желаемом выходе.

        bool flag = true

  

        // Переходим связанный список, начиная с заголовка.

        Node current = head; 

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

        

            if (flag == true) / * "<" ожидаемое отношение * /

            

                / * Если у нас такая ситуация, как A> B> C

                где A, B и C являются последовательными узлами

                в списке мы получаем A> B <C путем замены B

                и С * /

                if (current != null && 

                    current.next != null && 

                    current.data > current.next.data) 

                

                        temp = current.data; 

                        current.data = current.next.data; 

                        current.next.data = temp; 

                

            

            else / * ">" ожидаемое отношение * /

            

                / * Если у нас такая ситуация, как A <B <C, где

                A, B и C являются последовательными узлами в списке, который мы

                получить A <C> B, поменяв местами B и C * /

                if (current != null && 

                    current.next != null && 

                    current.data < current.next.data) 

                

                    temp = current.data; 

                    current.data = current.next.data; 

                    current.next.data = temp; 

                

            

  

            current = current.next; 

  

            / * флаг для обратной проверки * /

            flag = !(flag); 

        

    

  

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

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

    static void push( int new_data) 

    

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

        Node new_Node = new Node(); 

  

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

        new_Node.data = new_data; 

  

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

        new_Node.next = (head); 

  

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

        (head) = new_Node; 

    

  

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

    static void printList(Node Node) 

    

        while (Node != null

        

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

            Node = Node.next; 

        

        Console.WriteLine("NULL"); 

    

  

    / * Код водителя * /

    public static void Main() 

    

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

        // Node head = null;

  

        // создаем список 4 -> 3 -> 7 -> 8 -> 6 -> 2 -> 1

        // ответ должен быть -> 3 7 4 8 2 6 1

        push(1); 

        push(2); 

        push(6); 

        push(8); 

        push( 7); 

        push( 3); 

        push( 4); 

  

        Console.WriteLine("Given linked list "); 

        printList(head); 

  

        zigZagList(head); 

  

        Console.WriteLine("Zig Zag Linked list "); 

        printList(head); 

    


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


Выход :

Given linked list 
4->3->7->8->6->2->1->NULL

Zig Zag Linked list 
3->7->4->8->2->6->1->NULL 

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

Временная сложность: O (n)
Вспомогательное пространство: O (1)

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

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

Перегруппировать связанный список в зигзагообразном стиле

0.00 (0%) 0 votes