Рубрики

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

Учитывая односвязный список, напишите функцию для парной замены элементов.

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

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

Input : 1->NULL
Output : 1->NULL

Например, если связанный список 1-> 2-> 3-> 4-> 5, то функция должна изменить его на 2-> 1-> 4-> 3-> 5, и если связанный список тогда функция должна изменить его на.

МЕТОД 1 (итеративный)
Начните с головного узла и просмотрите список. При прохождении данных подкачки каждого узла с данными его следующего узла.

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

C ++

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

using namespace std;

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

class Node {

public:

    int data;

    Node* next;

};

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

void pairWiseSwap(Node* head)

{

    Node* temp = head;

  

    / * Пройдите дальше только если

    осталось как минимум два узла * /

    while (temp != NULL && temp->next != NULL) {

        / * Поменять местами данные узла с

           данные его следующего узла * /

        swap(temp->data,

             temp->next->data);

  

        / * Переместить темп на 2 для следующей пары * /

        temp = temp->next->next;

    }

}

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

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

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 * /

    push(&start, 5);

    push(&start, 4);

    push(&start, 3);

    push(&start, 2);

    push(&start, 1);

  

    cout << "Linked list "

         << "before calling pairWiseSwap()\n";

    printList(start);

  

    pairWiseSwap(start);

  

    cout << "\nLinked list "

         << "after calling pairWiseSwap()\n";

    printList(start);

  

    return 0;

}

  
// Этот код добавлен
// ратбхупендра

С

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

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

struct Node {

    int data;

    struct Node* next;

};

  
/ * Функция для замены двух целых чисел по адресам a и b * /

void swap(int* a, int* b);

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

void pairWiseSwap(struct Node* head)

{

    struct Node* temp = head;

  

    / * Пройдите дальше, только если осталось хотя бы два узла * /

    while (temp != NULL && temp->next != NULL) {

        / * Обмен данных узла с данными следующего узла * /

        swap(&temp->data, &temp->next->data);

  

        / * Переместить темп на 2 для следующей пары * /

        temp = temp->next->next;

    }

}

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

void swap(int* a, int* b)

{

    int temp;

    temp = *a;

    *a = *b;

    *b = temp;

}

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

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 * /

    push(&start, 5);

    push(&start, 4);

    push(&start, 3);

    push(&start, 2);

    push(&start, 1);

  

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

    printList(start);

  

    pairWiseSwap(start);

  

    printf("\nLinked list after calling  pairWiseSwap()\n");

    printList(start);

  

    return 0;

}

Джава

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

class LinkedList {

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

  

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

    class Node {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    void pairWiseSwap()

    {

        Node temp = head;

  

        / * Пройдите только до тех пор, пока не останется как минимум 2 узла * /

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

  

            / * Поменять местами данные * /

            int k = temp.data;

            temp.data = temp.next.data;

            temp.next.data = k;

            temp = temp.next.next;

        }

    }

  

    / * Сервисные функции * /

  

    / * Вставляет новый узел в начало списка. * /

    public 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();

  

        / * Создан связанный список 1-> 2-> 3-> 4-> 5 * /

        llist.push(5);

        llist.push(4);

        llist.push(3);

        llist.push(2);

        llist.push(1);

  

        System.out.println("Linked List before calling pairWiseSwap() ");

        llist.printList();

  

        llist.pairWiseSwap();

  

        System.out.println("Linked List after calling pairWiseSwap() ");

        llist.printList();

    }

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

питон

# Программа Python для парного обмена элементами связанного списка

  
# Класс узла

class Node:

  

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

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

  

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

    def __init__(self):

        self.head = None

  

    # Функция для парной замены элементов связанного списка

    def pairwiseSwap(self):

        temp = self.head

         

        # В списке ilnked нет узлов

        if temp is None:

            return 

           

        # Траверс фуртур, только если есть хотя бы два

        # осталось

        while(temp is not None and temp.next is not None):

  

            # Поменять местами данные узла с данными следующего узла

            temp.data, temp.next.data = temp.next.data, temp.data 

              

            # Переместить темо на 2 для следующей пары

            temp = temp.next.next

         

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

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

  

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

    def printList(self):

        temp = self.head

        while(temp):

            print temp.data,

            temp = temp.next

  

  
# Драйверная программа

llist = LinkedList()

llist.push(5)

llist.push(4)

llist.push(3)

llist.push(2)

llist.push(1)

  

print "Linked list before calling pairWiseSwap() "

llist.printList()

  
llist.pairwiseSwap()

  

print  "\nLinked list after calling pairWiseSwap()"

llist.printList()

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

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

using System;

class LinkedList {

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

  

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

    public class Node {

        public int data;

        public Node next;

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    void pairWiseSwap()

    {

        Node temp = head;

  

        / * Пройдите только до тех пор, пока не останется как минимум 2 узла * /

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

  

            / * Поменять местами данные * /

            int k = temp.data;

            temp.data = temp.next.data;

            temp.next.data = k;

            temp = temp.next.next;

        }

    }

  

    / * Сервисные функции * /

  

    / * Вставляет новый узел в начало списка. * /

    public 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();

  

        / * Создан связанный список 1-> 2-> 3-> 4-> 5 * /

        llist.push(5);

        llist.push(4);

        llist.push(3);

        llist.push(2);

        llist.push(1);

  

        Console.WriteLine("Linked List before calling pairWiseSwap() ");

        llist.printList();

  

        llist.pairWiseSwap();

  

        Console.WriteLine("Linked List after calling pairWiseSwap() ");

        llist.printList();

    }

}
// Этот код предоставлен Арнабом Кунду


Выход:

Linked List before calling pairWiseSwap() 
1 2 3 4 5 
Linked List after calling pairWiseSwap() 
2 1 4 3 5 

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

МЕТОД 2 (рекурсивный)
Если в связанном списке 2 или более 2 узлов, то поменяйте местами первые два узла и рекурсивно вызовите оставшуюся часть списка.

Ниже приведен пробный запуск вышеуказанного подхода:

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

/ * Рекурсивная функция для парной замены элементов

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

void pairWiseSwap(struct node* head)

{

    / * В списке должно быть как минимум два узла * /

    if (head != NULL && head->next != NULL) {

  

        / * Поменять местами данные узла с данными следующего узла * /

        swap(&head->data, &head->next->data);

  

        / * Вызовите pairWiseSwap () для остальной части списка * /

        pairWiseSwap(head->next->next);

    }

}

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

Решение обеспечивает обмен данными между узлами. Если данные содержат много полей, будет много операций подкачки. Смотрите это для реализации, которая изменяет ссылки, а не обменивается данными.

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

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

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

0.00 (0%) 0 votes