Рубрики

Имея связанный список, поменяйте местами альтернативные узлы и добавьте в конце

Получив связанный список, поменяйте местами альтернативные узлы и добавьте их в конец списка. Дополнительное допустимое пространство O (1)
Примеры

Input List:  1->2->3->4->5->6
Output List: 1->3->5->6->4->2

Input List:  12->14->16->18->20
Output List: 12->16->20->18->14

Идея состоит в том, чтобы поддерживать два связанных списка, один список всех узлов с нечетным расположением (1, 3, 5 в примере выше) и другой список всех узлов с четным расположением (6, 4 и 2 в примере выше). Ниже приведены подробные шаги.
1) Обходить данный связанный список, который считается нечетным списком. Следуйте за каждым посещенным узлом.
…… а) Если узел является четным узлом, удалите его из нечетного списка и добавьте его в начало списка четных узлов. Узлы добавляются спереди, чтобы сохранить обратный порядок.
2) Добавьте список четных узлов в конец списка нечетных узлов.

C ++

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

using namespace std;

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

class Node 

    public:

    int data; 

    Node *next; 

}; 

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

void rearrange(Node *odd) 

    // Если в связанном списке меньше 3

    // узлы, никаких изменений не требуется

    if (odd == NULL || odd->next == NULL || 

                    odd->next->next == NULL) 

        return

  

    // четные указатели на начало четного списка

    Node *even = odd->next; 

  

    // Удалить первый четный узел

    odd->next = odd->next->next; 

  

    // нечетные точки на следующий узел в нечетном списке

    odd = odd->next; 

  

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

    even->next = NULL; 

  

    // Обход списка

    while (odd && odd->next) 

    

    // Сохраняем следующий узел в нечетном списке

    Node *temp = odd->next->next; 

  

    // Связать следующий четный узел в

    // начало четного списка

    odd->next->next = even; 

    even = odd->next; 

  

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

    odd->next = temp; 

  

    // Переместить нечетный к следующему нечетному узлу

    if (temp != NULL) 

        odd = temp; 

    

  

    // Добавить четный список в конец нечетного списка

    odd->next = even; 

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

void 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; 

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

void printList(Node *node) 

    while (node != NULL) 

    

        cout<<node->data<<" "

        node = node->next; 

    

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

int main() 

    Node *start = NULL; 

  

    / * Составленный связанный список:

    1-> 2-> 3-> 4-> 5-> 6-> 7 * /

    push(&start, 7); 

    push(&start, 6); 

    push(&start, 5); 

    push(&start, 4); 

    push(&start, 3); 

    push(&start, 2); 

    push(&start, 1); 

  

    cout << "Linked list before calling rearrange() "

    printList(start); 

  

    rearrange(start); 

  

    cout << "\nLinked list after calling rearrange() "

    printList(start); 

  

    return 0; 

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

С

#include<stdio.h>
#include<stdlib.h>

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

struct Node

{

    int data;

    struct Node *next;

};

  
/ * Функция для реверса всех четных узлов и добавления в конце

   нечетный является головным узлом данного связанного списка * /

void rearrange(struct Node *odd)

{

    // Если связанный список имеет менее 3 узлов, никаких изменений не требуется

    if (odd == NULL || odd->next == NULL || odd->next->next == NULL)

        return;

  

    // четные указатели на начало четного списка

    struct Node *even = odd->next;

  

    // Удалить первый четный узел

    odd->next = odd->next->next;

  

    // нечетные точки на следующий узел в нечетном списке

    odd = odd->next;

  

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

    even->next = NULL;

  

    // Обход списка

    while (odd && odd->next)

    {

       // Сохраняем следующий узел в нечетном списке

       struct Node *temp = odd->next->next;

  

       // Ссылка следующего четного узла в начале четного списка

       odd->next->next = even;

       even = odd->next;

  

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

       odd->next = temp;

  

       // Переместить нечетный к следующему нечетному узлу

       if (temp != NULL)

         odd = temp;

    }

  

    // Добавить четный список в конец нечетного списка

    odd->next = even;

}

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

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 *node)

{

    while (node != NULL)

    {

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

        node = node->next;

    }

}

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

int main()

{

    struct Node *start = NULL;

  

    / * Составленный связанный список:

     1-> 2-> 3-> 4-> 5-> 6-> 7 * /

    push(&start, 7);

    push(&start, 6);

    push(&start, 5);

    push(&start, 4);

    push(&start, 3);

    push(&start, 2);

    push(&start, 1);

  

    printf("\n Linked list before calling  rearrange() ");

    printList(start);

  

    rearrange(start);

  

    printf("\n Linked list after calling  rearrange() ");

    printList(start);

  

    return 0;

}

Джава

// Java-программа для обращения к альтернативным узлам связанного списка
// и добавляем в конце

  

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int item) {

            data = item;

            next = null;

        }

    }

  

    / * Функция для реверса всех четных узлов и добавления в конце

     нечетный является головным узлом данного связанного списка * /

    void rearrange(Node odd) {

          

        // Если связанный список имеет менее 3 узлов, никаких изменений не требуется

        if (odd == null || odd.next == null || odd.next.next == null) {

            return;

        }

  

        // четные указатели на начало четного списка

        Node even = odd.next;

  

        // Удалить первый четный узел

        odd.next = odd.next.next;

  

        // нечетные точки на следующий узел в нечетном списке

        odd = odd.next;

  

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

        even.next = null;

  

        // Обход списка

        while (odd != null && odd.next != null) {

              

            // Сохраняем следующий узел в нечетном списке

            Node temp = odd.next.next;

  

            // Ссылка следующего четного узла в начале четного списка

            odd.next.next = even;

            even = odd.next;

  

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

            odd.next = temp;

  

            // Переместить нечетный к следующему нечетному узлу

            if (temp != null) {

                odd = temp;

            }

        }

  

        // Добавить четный список в конец нечетного списка

        odd.next = even;

    }

  

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

    void printList(Node node) {

        while (node != null) {

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

            node = node.next;

        }

    }

  

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        list.head = new Node(1);

        list.head.next = new Node(2);

        list.head.next.next = new Node(3);

        list.head.next.next.next = new Node(4);

        list.head.next.next.next.next = new Node(5);

        list.head.next.next.next.next.next = new Node(6);

        list.head.next.next.next.next.next.next = new Node(7);

  

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

        list.printList(head);

  

        System.out.println("");

        list.rearrange(head);

  

        System.out.println("Linked list after calling rearrange : ");

        list.printList(head);

  

    }

}

питон

# Программа Python для реверсирования альтернативных узлов и добавления
# в конце
# Допускается дополнительное пространство - O (1)

  
# Класс узла

class Node:

      

    # Конструктор для инициализации объекта узла

    def  __init__(self, data):

        self.data = data

        self.next = None

  
# Класс связанного списка содержит объект узла

class LinkedList:

      

    # Конструктор для инициализации головы

    def __init__(self):

        self.head = None

  

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

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head 

        self.head = new_node

  

      

    def printList(self):

        temp = self.head

        while(temp):

            print temp.data,

            temp = temp.next

  

    def rearrange(self):

          

        # Если в связанном списке менее 3 узлов, изменений нет

        # требуется для

        odd = self.head

        if (odd is None or odd.next is None or 

            odd.next.next is None):

            return 

  

        # Четные точки указывают на начало четного списка.

        even = odd.next

          

        # Удалить первый четный узел

        odd.next = odd.next.next

          

        # Нечетные точки для следующего узла в нечетном списке

        odd = odd.next 

          

        # Установить терминатор для четного списка

        even.next = None

      

        # Пройти список

        while (odd and odd.next):

            # Сохранить следующий узел в нечетном списке

            temp = odd.next.next

              

            # Связать следующий четный узел в начале

            № четного списка

            odd.next.next = even

            even = odd.next

  

            # Удалить четный узел из середины

            odd.next = temp

              

            # Переместить нечетное к следующему нечетному узлу

            if temp is not None:

                odd = temp

          

        # Добавить четный список в конец нечетного списка

        odd.next = even 

  
# Выполнение кода начинается здесь

if __name__ == '__main__':

    start = LinkedList()

      

    # Построенный связанный список есть;

    # 1-> 2-> 3-> 4-> 5-> 6-> 7

    start.push(7

    start.push(6)

    start.push(5)

    start.push(4)

    start.push(3)

    start.push(2)

    start.push(1)

      

    print "Linked list before calling  rearrange() "

    start.printList()

  

    start.rearrange()

  

    print "\nLinked list after calling  rearrange()"

    start.printList()

  
# Этот код предоставлен Нихилом Кумаром Сингхом (nickzuck_007)

C #

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

using System;

  

public class LinkedList 

{

  

    Node head;

  

    public class Node 

    {

  

        public int data;

        public Node next;

  

        public Node(int item) 

        {

            data = item;

            next = null;

        }

    }

  

    / * Функция, чтобы полностью изменить даже

    позиционируем узел и добавляем в конец

    нечетный является головным узлом данного связанного списка * /

    void rearrange(Node odd) 

    {

          

        // Если в связанном списке меньше 3

        // узлы, никаких изменений не требуется

        if (odd == null || odd.next == null ||

                        odd.next.next == null

        {

            return;

        }

  

        // четные указатели на начало четного списка

        Node even = odd.next;

  

        // Удалить первый четный узел

        odd.next = odd.next.next;

  

        // нечетные точки на следующий узел в нечетном списке

        odd = odd.next;

  

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

        even.next = null;

  

        // Обход списка

        while (odd != null && odd.next != null)

        {

              

            // Сохраняем следующий узел в нечетном списке

            Node temp = odd.next.next;

  

            // Связать следующий четный узел в

            // начало четного списка

            odd.next.next = even;

            even = odd.next;

  

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

            odd.next = temp;

  

            // Переместить нечетный к следующему нечетному узлу

            if (temp != null

            {

                odd = temp;

            }

        }

  

        // Добавить четный список в конец нечетного списка

        odd.next = even;

    }

  

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

    void printList(Node node)

    {

        while (node != null

        {

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

            node = node.next;

        }

    }

  

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

    public static void Main() 

    {

        LinkedList list = new LinkedList();

        list.head = new Node(1);

        list.head.next = new Node(2);

        list.head.next.next = new Node(3);

        list.head.next.next.next = new Node(4);

        list.head.next.next.next.next = new Node(5);

        list.head.next.next.next.next.next = new Node(6);

        list.head.next.next.next.next.next.next = new Node(7);

  

        Console.WriteLine("Linked list before calling rearrange : ");

        list.printList(list.head);

  

        Console.WriteLine("");

        list.rearrange(list.head);

  

        Console.WriteLine("Linked list after calling rearrange : ");

        list.printList(list.head);

    }

}

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


Выход:

 Linked list before calling  rearrange() 1 2 3 4 5 6 7
 Linked list after calling  rearrange()  1 3 5 7 6 4 2

Сложность времени: приведенный выше код просто пересекает данный связанный список. Таким образом, сложность времени O (n)

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

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

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

Имея связанный список, поменяйте местами альтернативные узлы и добавьте в конце

0.00 (0%) 0 votes