Рубрики

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

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

Примеры:

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

Input:   10->22->30->43->56->70
Output:  10->30->56->22->43->70

В этом вопросе важно убедиться, что все нижеуказанные случаи обрабатываются
1) Пустой связанный список
2) Связанный список только с одним узлом
3) Связанный список только с двумя узлами
4) Связанный список с нечетным числом узлов
5) Связанный список с четным числом узлов

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

C ++

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

using namespace std; 

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

class Node 

    public:

    int data; 

    Node* next; 

}; 

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

Node* newNode(int key) 

    Node *temp = new Node; 

    temp->data = key; 

    temp->next = NULL; 

    return temp; 

  
// Переставляем заданный связанный список так, чтобы все
// позиционированные узлы перед нечетным позиционированием.
// Возвращает новый заголовок связанного списка.
Node *rearrangeEvenOdd(Node *head) 

    // Угловой корпус

    if (head == NULL) 

        return NULL; 

  

    // Инициализируем первые узлы четных и

    // нечетные списки

    Node *odd = head; 

    Node *even = head->next; 

  

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

    // что мы можем соединить четный список на

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

    Node *evenFirst = even; 

  

    while (1) 

    

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

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

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

        if (!odd || !even || !(even->next)) 

        

            odd->next = evenFirst; 

            break

        

  

        // Соединяем нечетные узлы

        odd->next = even->next; 

        odd = even->next; 

  

        // Если после НЕТ больше нет четных узлов

        // текущий нечетный

        if (odd->next == NULL) 

        

            even->next = NULL; 

            odd->next = evenFirst; 

            break

        

  

        // Соединяем четные узлы

        even->next = odd->next; 

        even = odd->next; 

    

  

    return head; 

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

void printlist(Node * node) 

    while (node != NULL) 

    

        cout << node->data << "->"

        node = node->next; 

    

    cout << "NULL" << endl; 

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

int main(void

    Node *head = newNode(1); 

    head->next = newNode(2); 

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

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

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

  

    cout << "Given Linked List\n"

    printlist(head); 

  

    head = rearrangeEvenOdd(head); 

  

    cout << "Modified Linked List\n"

    printlist(head); 

  

    return 0; 

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

С

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

using namespace std;

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

struct Node

{

    int data;

    struct Node* next;

};

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

Node* newNode(int key)

{

    Node *temp = new Node;

    temp->data = key;

    temp->next = NULL;

    return temp;

}

  
// Переставляем заданный связанный список так, чтобы все
// позиционированные узлы перед нечетным позиционированием.
// Возвращает новый заголовок связанного списка.
Node *rearrangeEvenOdd(Node *head)
{

    // Угловой корпус

    if (head == NULL)

        return NULL;

  

    // Инициализируем первые узлы четных и

    // нечетные списки

    Node *odd = head;

    Node *even = head->next;

  

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

    // что мы можем соединить четный список на

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

    Node *evenFirst = even;

  

    while (1)

    {

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

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

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

        if (!odd || !even || !(even->next))

        {

            odd->next = evenFirst;

            break;

        }

  

        // Соединяем нечетные узлы

        odd->next = even->next;

        odd = even->next;

  

        // Если после НЕТ больше нет четных узлов

        // текущий нечетный

        if (odd->next == NULL)

        {

            even->next = NULL;

            odd->next = evenFirst;

            break;

        }

  

        // Соединяем четные узлы

        even->next = odd->next;

        even = odd->next;

    }

  

    return head;

}

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

void printlist(Node * node)

{

    while (node != NULL)

    {

        cout << node->data << "->";

        node = node->next;

    }

    cout << "NULL" << endl;

}

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

int main(void)

{

    Node *head = newNode(1);

    head->next = newNode(2);

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

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

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

  

    cout << "Given Linked List\n";

    printlist(head);

  

    head = rearrangeEvenOdd(head);

  

    cout << "\nModified Linked List\n";

    printlist(head);

  

    return 0;

}

Джава

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

class GfG 

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

static class Node 

    int data; 

    Node next; 

}

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

static Node newNode(int key) 

    Node temp = new Node(); 

    temp.data = key; 

    temp.next = null

    return temp; 

  
// Переставляет данный связанный список
// так, что все даже расположены
// узлы перед нечетным расположением.
// Возвращает новый заголовок связанного списка.

static Node rearrangeEvenOdd(Node head) 

    // Угловой корпус

    if (head == null

        return null

  

    // Инициализируем первые узлы четных и

    // нечетные списки

    Node odd = head; 

    Node even = head.next; 

  

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

    // что мы можем соединить четный список на

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

    Node evenFirst = even; 

  

    while (1 == 1

    

        // Если больше нет узлов,

        // затем подключаем первый узел четного

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

        if (odd == null || even == null ||

                        (even.next) == null

        

            odd.next = evenFirst; 

            break

        

  

        // Соединяем нечетные узлы

        odd.next = even.next; 

        odd = even.next; 

  

        // Если четных узлов больше НЕТ

        // после текущего нечетного

        if (odd.next == null

        

            even.next = null

            odd.next = evenFirst; 

            break

        

  

        // Соединяем четные узлы

        even.next = odd.next; 

        even = odd.next; 

    

    return head; 

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

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 = newNode(1); 

    head.next = newNode(2); 

    head.next.next = newNode(3); 

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

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

  

    System.out.println("Given Linked List"); 

    printlist(head); 

  

    head = rearrangeEvenOdd(head); 

  

    System.out.println("Modified Linked List"); 

    printlist(head); 

}

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

python3

# Python3 программа для реорганизации связанного списка
# таким образом, что все нечетное положение
# узел хранится до всех четных узлов

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

class Node: 

    def __init__(self, d):

        self.data = d

        self.next = None

  

class LinkedList:

    def __init__(self):

        self.head = None

          

    # Полезная функция для создания

    # новый узел

    def newNode(self, key): 

        temp = Node(key) 

        self.next = None

        return temp 

  

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

    # такое, что все даже позиционируются

    # узлы перед нечетным расположением.

    # Возвращает новый заголовок связанного списка.

    def rearrangeEvenOdd(self, head): 

          

        # Угловой кейс

        if (self.head == None): 

            return None

  

        # Инициализировать первые узлы

        # четные и нечетные списки

        odd = self.head 

        even = self.head.next

  

        # Помните первый узел четного списка так

        # что мы можем подключить четный список на

        # конец нечетного списка.

        evenFirst = even 

  

        while (1 == 1): 

              

            # Если больше нет узлов,

            # затем подключите первый узел четного

            # список до последнего узла нечетного списка

            if (odd == None or even == None or 

                              (even.next) == None): 

                odd.next = evenFirst 

                break

  

            # Подключение нечетных узлов

            odd.next = even.next

            odd = even.next

  

            # Если четных узлов больше НЕТ

            # после текущего нечетного.

            if (odd.next == None): 

                even.next = None

                odd.next = evenFirst 

                break

  

            # Подключение четных узлов

            even.next = odd.next

            even = odd.next

        return head

  

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

    def printlist(self, node): 

        while (node != None): 

            print(node.data, end = "")

            print("->", end = "")

            node = node.next

        print ("NULL")

          

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

    # с начала

    def push(self, new_data): 

        new_node = Node(new_data) 

        new_node.next = self.head 

        self.head = new_node

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

ll = LinkedList()

ll.push(5)

ll.push(4)

ll.push(3)

ll.push(2)

ll.push(1)

print ("Given Linked List")

ll.printlist(ll.head) 

  

start = ll.rearrangeEvenOdd(ll.head) 

  

print ("\nModified Linked List")

ll.printlist(start)

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

C #

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

using System;

  

class GfG 

  

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

    class Node 

    

        public int data; 

        public Node next; 

    

  

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

    static Node newNode(int key) 

    

        Node temp = new Node(); 

        temp.data = key; 

        temp.next = null

        return temp; 

    

  

    // Переставляет данный связанный список

    // так, что все даже расположены

    // узлы перед нечетным расположением.

    // Возвращает новый заголовок связанного списка.

    static Node rearrangeEvenOdd(Node head) 

    

        // Угловой корпус

        if (head == null

            return null

  

        // Инициализируем первые узлы четных и

        // нечетные списки

        Node odd = head; 

        Node even = head.next; 

  

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

        // что мы можем соединить четный список на

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

        Node evenFirst = even; 

  

        while (1 == 1) 

        

            // Если больше нет узлов,

            // затем подключаем первый узел четного

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

            if (odd == null || even == null || 

                            (even.next) == null

            

                odd.next = evenFirst; 

                break

            

  

            // Соединяем нечетные узлы

            odd.next = even.next; 

            odd = even.next; 

  

            // Если четных узлов больше НЕТ

            // после текущего нечетного

            if (odd.next == null

            

                even.next = null

                odd.next = evenFirst; 

                break

            

  

            // Соединяем четные узлы

            even.next = odd.next; 

            even = odd.next; 

        

        return head; 

    

  

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

    static void printlist(Node node) 

    

        while (node != null

        

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

            node = node.next; 

        

        Console.WriteLine("NULL") ; 

    

  

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

    public static void Main() 

    

        Node head = newNode(1); 

        head.next = newNode(2); 

        head.next.next = newNode(3); 

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

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

  

        Console.WriteLine("Given Linked List"); 

        printlist(head); 

  

        head = rearrangeEvenOdd(head); 

  

        Console.WriteLine("Modified Linked List"); 

        printlist(head); 

    

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


Выход:

Given Linked List
1->2->3->4->5->NULL
Modified Linked List
1->3->5->2->4->NULL

Эта статья предоставлена Harsh Parikh. Пожалуйста, посмотрите здесь другой код, предоставленный Gautam Singh. Если вам нравится GeeksforGeeks и вы хотели бы внести свой вклад, вы также можете написать статью и отправить свою статью по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

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

0.00 (0%) 0 votes