Рубрики

Разделять четные и нечетные узлы в связанном списке

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

Примеры:

Input: 17->15->8->12->10->5->4->1->7->6->NULL
Output: 8->12->10->4->6->17->15->5->1->7->NULL

Input: 8->12->10->5->4->1->6->NULL
Output: 8->12->10->4->6->5->1->NULL

// If all numbers are even then do not change the list
Input: 8->12->10->NULL
Output: 8->12->10->NULL

// If all numbers are odd then do not change the list
Input: 1->3->5->7->NULL
Output: 1->3->5->7->NULL

Способ 1
Идея состоит в том, чтобы получить указатель на последний узел списка. Затем просмотрите список, начиная с головного узла, и переместите нечетные узлы из их текущей позиции в конец списка.

Спасибо бандербою за предложение этого метода.

Алгоритм:
… 1) Получить указатель на последний узел.
… 2) Переместить все нечетные узлы в конец.
…… ..a) Рассмотрим все нечетные узлы перед первым четным узлом и переместим их в конец.
…… ..b) Измените указатель головы так, чтобы он указывал на первый четный узел.
…… ..b) Рассмотрим все нечетные узлы после первого четного узла и переместим их в конец.

C ++

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

using namespace std;

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

class Node 

    public:

    int data; 

    Node *next; 

}; 

  

void segregateEvenOdd(Node **head_ref) 

    Node *end = *head_ref; 

    Node *prev = NULL; 

    Node *curr = *head_ref; 

  

    / * Получить указатель на последний узел * /

    while (end->next != NULL) 

        end = end->next; 

  

    Node *new_end = end; 

  

    / * Рассмотрим все нечетные узлы перед первым

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

    while (curr->data % 2 != 0 && curr != end) 

    

        new_end->next = curr; 

        curr = curr->next; 

        new_end->next->next = NULL; 

        new_end = new_end->next; 

    

  

    // 10-> 8-> 17-> 17-> 15

    / * Делайте следующие шаги только если

    есть какой-то четный узел * /

    if (curr->data%2 == 0) 

    

        / * Изменить указатель головы на

        указать на первый четный узел * /

        *head_ref = curr; 

  

        / * теперь текущие указывает на

        первый четный узел * /

        while (curr != end) 

        

            if ( (curr->data) % 2 == 0 ) 

            

                prev = curr; 

                curr = curr->next; 

            

            else

            

                / * разорвать связь между

                предыдущий и текущий * /

                prev->next = curr->next; 

  

                / * Сделать следующий из curr как NULL * /

                curr->next = NULL; 

  

                / * Переместить курсор в конец * /

                new_end->next = curr; 

  

                / * сделать curr новым концом списка * /

                new_end = curr; 

  

                / * Обновить текущий указатель на

                следующий из перемещенного узла * /

                curr = prev->next; 

            

        

    

  

    / * Перед выполнением мы должны установить значение prev

    строки, следующие за этим утверждением * /

    else prev = curr; 

  

    / * Если существует более 1 нечетных узлов

    и конец оригинального списка нечетный, то

    переместить этот узел в конец, чтобы сохранить

    тот же порядок нечетных чисел в измененном списке * /

    if (new_end != end && (end->data) % 2 != 0) 

    

        prev->next = end->next; 

        end->next = NULL; 

        new_end->next = end; 

    

    return

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

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* head = NULL; 

  

    / * Давайте создадим пример связанного списка следующим образом

    0-> 2-> 4-> 6-> 8-> 10-> 11 * /

  

    push(&head, 11); 

    push(&head, 10); 

    push(&head, 8); 

    push(&head, 6); 

    push(&head, 4); 

    push(&head, 2); 

    push(&head, 0); 

  

    cout << "Original Linked list "

    printList(head); 

  

    segregateEvenOdd(&head); 

  

    cout << "\nModified Linked list "

    printList(head); 

  

    return 0; 

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

С

// C-программа для разделения четных и нечетных узлов в
// Связанный список
#include <stdio.h>
#include <stdlib.h>

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

struct Node

{

    int data;

    struct Node *next;

};

  

void segregateEvenOdd(struct Node **head_ref)

{

    struct Node *end = *head_ref;

    struct Node *prev = NULL;

    struct Node *curr = *head_ref;

  

    / * Получить указатель на последний узел * /

    while (end->next != NULL)

        end = end->next;

  

    struct Node *new_end = end;

  

    / * Рассмотрим все нечетные узлы перед первым четным узлом

       и двигаться затем после завершения * /

    while (curr->data %2 != 0 && curr != end)

    {

        new_end->next = curr;

        curr = curr->next;

        new_end->next->next = NULL;

        new_end = new_end->next;

    }

  

    // 10-> 8-> 17-> 17-> 15

    / * Выполнять следующие шаги, только если есть какой-либо четный узел * /

    if (curr->data%2 == 0)

    {

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

        *head_ref = curr;

  

        / * теперь текущие точки указывают на первый четный узел * /

        while (curr != end)

        {

            if ( (curr->data)%2 == 0 )

            {

                prev = curr;

                curr = curr->next;

            }

            else

            {

                / * разорвать связь между предыдущим и текущим * /

                prev->next = curr->next;

  

                / * Сделать следующий из curr как NULL * /

                curr->next = NULL;

  

                / * Переместить курсор в конец * /

                new_end->next = curr;

  

                / * сделать curr новым концом списка * /

                new_end = curr;

  

                / * Обновить текущий указатель на следующий перемещенный узел * /

                curr = prev->next;

            }

        }

    }

  

    / * Перед выполнением строк, следующих за этим, мы должны установить prev

       заявление */

    else prev = curr;

  

    / * Если существует более 1 нечетных узлов и конец исходного списка

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

      номера в измененном списке * /

    if (new_end!=end && (end->data)%2 != 0)

    {

        prev->next = end->next;

        end->next = NULL;

        new_end->next = end;

    }

    return;

}

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

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* head = NULL;

  

    / * Давайте создадим пример связанного списка следующим образом

      0-> 2-> 4-> 6-> 8-> 10-> 11 * /

  

    push(&head, 11);

    push(&head, 10);

    push(&head, 8);

    push(&head, 6);

    push(&head, 4);

    push(&head, 2);

    push(&head, 0);

  

    printf("\nOriginal Linked list \n");

    printList(head);

  

    segregateEvenOdd(&head);

  

    printf("\nModified Linked list \n");

    printList(head);

  

    return 0;

}

Джава

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

class LinkedList

{

    Node head;  // заголовок списка

  

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

    class Node

    {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    void segregateEvenOdd()

    {

        Node end = head;

        Node prev = null;

        Node curr = head;

  

        / * Получить указатель на последний узел * /

        while (end.next != null)

            end = end.next;

  

        Node new_end = end;

  

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

        while (curr.data %2 !=0 && curr != end)

        {

            new_end.next = curr;

            curr = curr.next;

            new_end.next.next = null;

            new_end = new_end.next;

        }

  

        // делать следующие шаги, только если есть четный узел

        if (curr.data %2 ==0)

        {

            head = curr;

  

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

            while (curr != end)

            {

                if (curr.data % 2 == 0)

                {

                    prev = curr;

                    curr = curr.next;

                }

                else

                {

                    / * Разорвать связь между предыдущим и текущим * /

                    prev.next = curr.next;

  

                    / * Сделать следующий из curr как ноль * /

                    curr.next = null;

  

                    / * Переместить курсор в конец * /

                    new_end.next = curr;

  

                    / * Сделать curr новым концом списка * /

                    new_end = curr;

  

                    / * Обновить указатель курсора * /

                    curr = prev.next;

                }

            }

        }

  

        / * Мы должны установить prev перед выполнением остальной части этого кода * /

        else prev = curr;

  

        if (new_end != end && end.data %2 != 0)

        {

            prev.next = end.next;

            end.next = null;

            new_end.next = end;

        }

    }

  

    / * Дана ссылка (указатель на указатель) на голову

        списка и int, нажмите новый узел на передней панели

        из списка. * /

    void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                  Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

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

        head = new_node;

    }

  

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

    void printList()

    {

        Node temp = head;

        while(temp != null)

        {

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

            temp = temp.next;

        }

        System.out.println();

    }

  

  

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

    public static void main(String args[])

    {

        LinkedList llist = new LinkedList();

        llist.push(11);

        llist.push(10);

        llist.push(8);

        llist.push(6);

        llist.push(4);

        llist.push(2);

        llist.push(0);

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

        llist.printList();

  

        llist.segregateEvenOdd();

  

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

        llist.printList();

    }

} / * Этот код предоставлен Раджатом Мишрой * /

C #

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

using System;

  

public class LinkedList

{

    Node head; // заголовок списка

  

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

    public class Node

    {

        public int data;

        public Node next;

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    void segregateEvenOdd()

    {

        Node end = head;

        Node prev = null;

        Node curr = head;

  

        / * Получить указатель на последний узел * /

        while (end.next != null)

            end = end.next;

  

        Node new_end = end;

  

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

        // получение первого узла

        while (curr.data % 2 != 0 && curr != end)

        {

            new_end.next = curr;

            curr = curr.next;

            new_end.next.next = null;

            new_end = new_end.next;

        }

  

        // делаем только следующие шаги

        // если есть четный узел

        if (curr.data % 2 == 0)

        {

            head = curr;

  

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

            while (curr != end)

            {

                if (curr.data % 2 == 0)

                {

                    prev = curr;

                    curr = curr.next;

                }

                else

                {

                    / * Разорвать связь между предыдущим и текущим * /

                    prev.next = curr.next;

  

                    / * Сделать следующий из curr как ноль * /

                    curr.next = null;

  

                    / * Переместить курсор в конец * /

                    new_end.next = curr;

  

                    / * Сделать curr новым концом списка * /

                    new_end = curr;

  

                    / * Обновить указатель курсора * /

                    curr = prev.next;

                }

            }

        }

  

        / * Мы должны установить предыдущий

        выполнение остальной части этого кода * /

        else prev = curr;

  

        if (new_end != end && end.data % 2 != 0)

        {

            prev.next = end.next;

            end.next = null;

            new_end.next = end;

        }

    }

  

    / * Дана ссылка (указатель на указатель) на голову

        списка и int, нажмите новый узел на передней панели

        из списка. * /

    void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

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

        head = new_node;

    }

  

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

    void printList()

    {

        Node temp = head;

        while(temp != null)

        {

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

            temp = temp.next;

        }

        Console.WriteLine();

    }

  

  

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

    public static void Main(String []args)

    {

        LinkedList llist = new LinkedList();

        llist.push(11);

        llist.push(10);

        llist.push(8);

        llist.push(6);

        llist.push(4);

        llist.push(2);

        llist.push(0);

        Console.WriteLine("Origional Linked List");

        llist.printList();

  

        llist.segregateEvenOdd();

  

        Console.WriteLine("Modified Linked List");

        llist.printList();

    }

}

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


Выход:

 Original Linked list 0 2 4 6 8 10 11
 Modified Linked list 0 2 4 6 8 10 11

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

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

C ++

// Программа CPP для разделения четных и нечетных узлов в
// Связанный список
#include <stdio.h>
#include <stdlib.h>

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

struct Node

{

    int data;

    struct Node *next;

};

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

void segregateEvenOdd(struct Node **head_ref)

{

    // Начальный узел списка, имеющий

    // четные значения.

    Node *evenStart = NULL;

      

    // Конечный узел списка четных значений.

    Node *evenEnd = NULL;

      

    // Начальный узел списка нечетных значений.

    Node *oddStart = NULL;

      

    // Конечный узел списка нечетных значений.

    Node *oddEnd = NULL;

      

    // Узел для обхода списка.

    Node *currNode = *head_ref;

      

    while(currNode != NULL){

        int val = currNode -> data;

          

        // Если текущее значение четное, добавить

        // это список четных значений.

        if(val % 2 == 0) {

            if(evenStart == NULL){

                evenStart = currNode;

                evenEnd = evenStart;

            }

              

            else{

                evenEnd -> next = currNode;

                evenEnd = evenEnd -> next;

            }

        

          

        // Если текущее значение нечетное, добавить

        // это список нечетных значений.

        else{

            if(oddStart == NULL){

                oddStart = currNode;

                oddEnd = oddStart;

            }

            else{

                oddEnd -> next = currNode;

                oddEnd = oddEnd -> next;

            }

        }

                      

        // Переместить указатель головы на один шаг вперед

        // прямое направление

        currNode = currNode -> next;    

    }

      

    // Если нечетный список или четный список пуст,

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

    // четные или нечетные

    if(oddStart == NULL || evenStart == NULL){

        return;

    }

      

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

    evenEnd -> next = oddStart;

    oddEnd -> next = NULL;

      

    // Изменить указатель головы на

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

    *head_ref = evenStart;

}

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

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* head = NULL;

  

    / * Давайте создадим пример связанного списка следующим образом

    0-> 1-> 4-> 6-> 9-> 10-> 11 * /

  

    push(&head, 11);

    push(&head, 10);

    push(&head, 9);

    push(&head, 6);

    push(&head, 4);

    push(&head, 1);

    push(&head, 0);

  

    printf("\nOriginal Linked list \n");

    printList(head);

  

    segregateEvenOdd(&head);

  

    printf("\nModified Linked list \n");

    printList(head);

  

    return 0;

}

  
// Этот код предоставлен NIKHIL JINDAL.

Джава

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

import java.io.*;

  

class LinkedList {

      

    Node head;  // заголовок списка

   

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

    class Node

    {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

      

    public void segregateEvenOdd() {

          

        Node evenStart = null;

        Node evenEnd = null;

        Node oddStart = null;

        Node oddEnd = null;

        Node currentNode = head;

          

        while(currentNode != null) {

            int element = currentNode.data;

              

            if(element % 2 == 0) {

                  

                if(evenStart == null) {

                    evenStart = currentNode;

                    evenEnd = evenStart;

                } else {

                    evenEnd.next = currentNode;

                    evenEnd = evenEnd.next;

                }

                  

            } else {

                  

                if(oddStart == null) {

                    oddStart = currentNode;

                    oddEnd = oddStart;

                } else {

                    oddEnd.next = currentNode;

                    oddEnd = oddEnd.next;

                }

            }

                        // Переместить указатель головы на один шаг вперед

            currentNode = currentNode.next;    

        }

          

          

        if(oddStart == null || evenStart == null) {

            return;

        }

          

        evenEnd.next = oddStart;

        oddEnd.next = null;

        head=evenStart;

    }

      

    / * Дана ссылка (указатель на указатель) на голову

        списка и int, нажмите новый узел на передней панели

        из списка. * /

    void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                  Введите данные * /

        Node new_node = new Node(new_data);

   

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

   

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

        head = new_node;

    }

   

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

    void printList()

    {

        Node temp = head;

        while(temp != null)

        {

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

            temp = temp.next;

        }

        System.out.println();

    }

      

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

    public static void main(String args[])

    {

        LinkedList llist = new LinkedList();

        llist.push(11);

        llist.push(10);

        llist.push(9);

        llist.push(6);

        llist.push(4);

        llist.push(1);

        llist.push(0);

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

        llist.printList();

   

        llist.segregateEvenOdd();

   

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

        llist.printList();

    }

}

C #

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

using System;

      

public class LinkedList

{

      

    Node head; // заголовок списка

  

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

    public class Node

    {

        public int data;

        public Node next;

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

      

    public void segregateEvenOdd() 

    {

          

        Node evenStart = null;

        Node evenEnd = null;

        Node oddStart = null;

        Node oddEnd = null;

        Node currentNode = head;

          

        while(currentNode != null

        {

            int element = currentNode.data;

              

            if(element % 2 == 0) 

            {

                  

                if(evenStart == null

                {

                    evenStart = currentNode;

                    evenEnd = evenStart;

                }

                else

                {

                    evenEnd.next = currentNode;

                    evenEnd = evenEnd.next;

                }

                  

            

            else

            {

                  

                if(oddStart == null)

                {

                    oddStart = currentNode;

                    oddEnd = oddStart;

                }

                else

                {

                    oddEnd.next = currentNode;

                    oddEnd = oddEnd.next;

                }

            }

          

        // Переместить указатель головы на один шаг вперед

            currentNode = currentNode.next; 

        }

          

          

        if(oddStart == null || evenStart == null)

        {

            return;

        }

          

        evenEnd.next = oddStart;

        oddEnd.next = null;

        head=evenStart;

    }

      

    / * Дана ссылка (указатель на указатель) на голову

        списка и int, нажмите новый узел на передней панели

        из списка. * /

    void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

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

        head = new_node;

    }

  

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

    void printList()

    {

        Node temp = head;

        while(temp != null)

        {

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

            temp = temp.next;

        }

        Console.WriteLine();

    }

      

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

    public static void Main()

    {

        LinkedList llist = new LinkedList();

        llist.push(11);

        llist.push(10);

        llist.push(9);

        llist.push(6);

        llist.push(4);

        llist.push(1);

        llist.push(0);

        Console.WriteLine("Origional Linked List");

        llist.printList();

  

        llist.segregateEvenOdd();

  

        Console.WriteLine("Modified Linked List");

        llist.printList();

    }

}

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



Выход:

Origional Linked List
0 1 4 6 9 10 11 
Modified Linked List
0 4 6 10 1 9 11 

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

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

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

Разделять четные и нечетные узлы в связанном списке

0.00 (0%) 0 votes