Рубрики

Реверс четных элементов в связанном списке

Рекурсия, Связанный список

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

Input: 1 -> 2 -> 3 -> 3 -> 4 -> 6 -> 8 -> 5 -> NULL
Output: 1 2 3 3 8 6 4 5
Initial list: 1 -> 2 -> 3 -> 3 -> 4 -> 6 -> 8 -> 5 -> NULL
Reversed list: 1 -> 2 -> 3 -> 3 -> 8 -> 6 -> 4 -> 5 -> NULL

Input: 11 -> 32 -> 7 -> NULL
Output: 11 32 7

Подход: Реверсирование смежных четных элементов не произойдет, когда:

  1. Значение узла нечетное.
  2. Значение узла является четным, но смежные значения являются нечетными.

В остальных случаях непрерывный блок четных узлов может быть обращен вспять.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <iostream>

using namespace std;

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

struct node {

    int data;

    struct node* next;

};

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

struct node* newNode(int d)

{

    struct node* newnode = new node();

    newnode->data = d;

    newnode->next = NULL;

    return newnode;

}

  
// Рекурсивная функция для обратного последовательного
// четные узлы связанного списка

struct node* reverse(struct node* head, struct node* prev)

{

  

    // Базовый вариант

    if (head == NULL)

        return NULL;

  

    struct node* temp;

    struct node* curr;

    curr = head;

  

    // реверсирование узлов до значения узла curr

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

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

        temp = curr->next;

        curr->next = prev;

        prev = curr;

        curr = temp;

    }

  

    // Если элементы были перевернуты, то голова

    // указатель должен быть изменен

    if (curr != head) {

  

        head->next = curr;

  

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

        curr = reverse(curr, NULL);

        return prev;

    }

  

    // Просто перебираем узлы нечетных значений

    else {

        head->next = reverse(head->next, head);

        return head;

    }

}

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

void printLinkedList(struct node* head)

{

    while (head != NULL) {

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

        head = head->next;

    }

}

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

int main()

{

    int arr[] = { 1, 2, 3, 3, 4, 6, 8, 5 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    struct node* head = NULL;

    struct node* p;

  

    // Построение связанного списка

    for (int i = 0; i < n; i++) {

  

        if (head == NULL) {

            p = newNode(arr[i]);

            head = p;

            continue;

        }

        p->next = newNode(arr[i]);

        p = p->next;

    }

  

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

    head = reverse(head, NULL);

  

    // Печать перевернутого связанного списка

    printLinkedList(head);

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.*;

  

class GFG

{

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

static class node

{

    int data;

    node next;

};

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

static node newNode(int d)

{

    node newnode = new node();

    newnode.data = d;

    newnode.next = null;

    return newnode;

}

  
// Рекурсивная функция для обратного последовательного
// четные узлы связанного списка

static node reverse(node head, node prev)

{

  

    // Базовый вариант

    if (head == null)

        return null;

  

    node temp;

    node curr;

    curr = head;

  

    // реверсирование узлов до значения узла curr

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

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

    {

        temp = curr.next;

        curr.next = prev;

        prev = curr;

        curr = temp;

    }

  

    // Если элементы были перевернуты, то голова

    // указатель должен быть изменен

    if (curr != head) 

    {

        head.next = curr;

  

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

        curr = reverse(curr, null);

        return prev;

    }

  

    // Просто перебираем узлы нечетных значений

    else

    {

        head.next = reverse(head.next, head);

        return head;

    }

}

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

static void printLinkedList(node head)

{

    while (head != null)

    {

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

        head = head.next;

    }

}

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

public static void main(String[] args)

{

    int arr[] = { 1, 2, 3, 3, 4, 6, 8, 5 };

    int n = arr.length;

  

    node head = null;

    node p = new node();

  

    // Построение связанного списка

    for (int i = 0; i < n; i++)

    {

        if (head == null) 

        {

            p = newNode(arr[i]);

            head = p;

            continue;

        }

        p.next = newNode(arr[i]);

        p = p.next;

    }

  

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

    head = reverse(head, null);

  

    // Печать перевернутого связанного списка

    printLinkedList(head);

}
} 

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

C #

// C # реализация вышеуказанного подхода

using System;

  

class GFG

{

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

public class node

{

    public int data;

    public node next;

};

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

static node newNode(int d)

{

    node newnode = new node();

    newnode.data = d;

    newnode.next = null;

    return newnode;

}

  
// Рекурсивная функция для обратного последовательного
// четные узлы связанного списка

static node reverse(node head, node prev)

{

  

    // Базовый вариант

    if (head == null)

        return null;

  

    node temp;

    node curr;

    curr = head;

  

    // реверсирование узлов до значения узла curr

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

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

    {

        temp = curr.next;

        curr.next = prev;

        prev = curr;

        curr = temp;

    }

  

    // Если элементы были перевернуты, то голова

    // указатель должен быть изменен

    if (curr != head) 

    {

        head.next = curr;

  

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

        curr = reverse(curr, null);

        return prev;

    }

  

    // Просто перебираем узлы нечетных значений

    else

    {

        head.next = reverse(head.next, head);

        return head;

    }

}

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

static void printLinkedList(node head)

{

    while (head != null)

    {

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

        head = head.next;

    }

}

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

public static void Main(String[] args)

{

    int []arr = { 1, 2, 3, 3, 4, 6, 8, 5 };

    int n = arr.Length;

  

    node head = null;

    node p = new node();

  

    // Построение связанного списка

    for (int i = 0; i < n; i++)

    {

        if (head == null) 

        {

            p = newNode(arr[i]);

            head = p;

            continue;

        }

        p.next = newNode(arr[i]);

        p = p.next;

    }

  

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

    head = reverse(head, null);

  

    // Печать перевернутого связанного списка

    printLinkedList(head);

}
}

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

Выход:

1 2 3 3 8 6 4 5

Сложность времени: O (N)
Космическая сложность: O (1)

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

Реверс четных элементов в связанном списке

0.00 (0%) 0 votes