Рубрики

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

Связанный список

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

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

C ++

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

  
#include <bits/stdc++.h>

using namespace std;

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

class node {

public:

    int data;

    node* next;

};

  
/ * Функция для парной замены элементов
связанного списка. Возвращается глава
измененный список, поэтому возвращаемое значение
этого узла должен быть назначен * /
node* pairWiseSwap(node* head)
{

    // Базовый случай: список пуст или имеет только один узел

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

        return head;

  

    // Сохранить заголовок списка после двух узлов

    node* remaing = head->next->next;

  

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

    node* newhead = head->next;

  

    // Изменить следующий из второго узла

    head->next->next = head;

  

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

    head->next = pairWiseSwap(remaing);

  

    // Возвращаем новую голову изменённого списка

    return newhead;

}

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

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 pairWiseSwap() ";

    printList(start);

  

    start = pairWiseSwap(start); // Обратите внимание на это изменение

  

    cout << "\nLinked list after calling pairWiseSwap() ";

    printList(start);

  

    return 0;

}

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

С

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

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

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

struct Node {

    int data;

    struct Node* next;

};

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

void pairWiseSwap(struct Node** head)

{

    // Если связанный список пуст или в списке только один узел

    if (*head == NULL || (*head)->next == NULL)

        return;

  

    // Инициализируем предыдущие и текущие указатели

    struct Node* prev = *head;

    struct Node* curr = (*head)->next;

  

    *head = curr; // Изменить голову перед продолжением

  

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

    while (true) {

        struct Node* next = curr->next;

        curr->next = prev; // Изменить следующий из текущего как предыдущий узел

  

        // Если next NULL или next - последний узел

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

            prev->next = next;

            break;

        }

  

        // Изменить следующий предыдущий следующий следующий

        prev->next = next->next;

  

        // Обновить предыдущий и текущий

        prev = next;

        curr = prev->next;

    }

}

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

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;

    }

}

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

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  pairWiseSwap() ");

    printList(start);

  

    pairWiseSwap(&start);

  

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

    printList(start);

  

    getchar();

    return 0;

}

Джава

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

  

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

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

    Node pairWiseSwap(Node node)

    {

  

        // Если связанный список пуст или в списке только один узел

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

            return node;

        }

  

        // Инициализируем предыдущие и текущие указатели

        Node prev = node;

        Node curr = node.next;

  

        node = curr; // Изменить голову перед продолжением

  

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

        while (true) {

            Node next = curr.next;

            curr.next = prev; // Изменить следующий из текущего как предыдущий узел

  

            // Если next NULL или next - последний узел

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

                prev.next = next;

                break;

            }

  

            // Изменить следующий предыдущий следующий следующий

            prev.next = next.next;

  

            // Обновить предыдущий и текущий

            prev = next;

            curr = prev.next;

        }

        return node;

    }

  

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

    void printList(Node node)

    {

        while (node != null) {

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

            node = node.next;

        }

    }

  

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

    public static void main(String[] args)

    {

  

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

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

        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 pairwiseSwap() ");

        list.printList(head);

        Node st = list.pairWiseSwap(head);

        System.out.println("");

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

        list.printList(st);

        System.out.println("");

    }

}

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

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;

        }

    }

  

    / * Функция для парного обмена

    элементы связанного списка * /

    Node pairWiseSwap(Node node)

    {

  

        // Если связанный список пуст или существует

        // только один узел в списке

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

            return node;

        }

  

        // Инициализируем предыдущие и текущие указатели

        Node prev = node;

        Node curr = node.next;

  

        // Изменить голову перед продолжением

        node = curr;

  

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

        while (true) {

            Node next = curr.next;

  

            // Изменить следующий из текущего как предыдущий узел

            curr.next = prev;

  

            // Если next NULL или next - последний узел

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

                prev.next = next;

                break;

            }

  

            // Изменить следующий предыдущий следующий следующий

            prev.next = next.next;

  

            // Обновить предыдущий и текущий

            prev = next;

            curr = prev.next;

        }

        return node;

    }

  

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

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

    void printList(Node node)

    {

        while (node != null) {

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

            node = node.next;

        }

    }

  

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

    public static void Main(String[] args)

    {

  

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

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

        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 pairwiseSwap() ");

        list.printList(list.head);

        Node st = list.pairWiseSwap(list.head);

        Console.WriteLine("");

        Console.WriteLine("Linked list after calling pairwiseSwap() ");

        list.printList(st);

        Console.WriteLine("");

    }

}

  
// Этот код предоставлен Rajput-Ji

Выход:

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

Сложность времени: временная сложность вышеупомянутой программы O (n), где n — количество узлов в данном связанном списке. Цикл while выполняет обход заданного связанного списка.

Ниже приводится рекурсивная реализация того же подхода. Мы меняем первые два узла и возвращаемся к оставшемуся списку. Спасибо Компьютерщику и Омеру Салему за предложение этого метода.

C ++

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

  
#include <bits/stdc++.h>

using namespace std;

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

class node {

public:

    int data;

    node* next;

};

  
/ * Функция для парной замены элементов связанного списка.
Возвращает заголовок измененного списка, поэтому возвращаемое значение
этого узла должен быть назначен * /
node* pairWiseSwap(node* head)
{

    // Базовый случай: список пуст или имеет только один узел

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

        return head;

  

    // Сохранить заголовок списка после двух узлов

    node* remaing = head->next->next;

  

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

    node* newhead = head->next;

  

    // Изменить следующий из второго узла

    head->next->next = head;

  

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

    head->next = pairWiseSwap(remaing);

  

    // Возвращаем новую голову изменённого списка

    return newhead;

}

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

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;

    }

}

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

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 pairWiseSwap() ";

    printList(start);

  

    start = pairWiseSwap(start); // Обратите внимание на это изменение

  

    cout << "\nLinked list after calling pairWiseSwap() ";

    printList(start);

  

    return 0;

}

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

С

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

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

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

struct node {

    int data;

    struct node* next;

};

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

   Возвращает заголовок измененного списка, поэтому возвращаемое значение

   этого узла должен быть назначен * /

struct node* pairWiseSwap(struct node* head)

{

    // Базовый случай: список пуст или имеет только один узел

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

        return head;

  

    // Сохранить заголовок списка после двух узлов

    struct node* remaing = head->next->next;

  

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

    struct node* newhead = head->next;

  

    // Изменить следующий из второго узла

    head->next->next = head;

  

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

    head->next = pairWiseSwap(remaing);

  

    // Возвращаем новую голову изменённого списка

    return newhead;

}

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

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;

    }

}

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

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  pairWiseSwap() ");

    printList(start);

  

    start = pairWiseSwap(start); // Обратите внимание на это изменение

  

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

    printList(start);

  

    return 0;

}

Джава

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

  

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

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

     Возвращает заголовок измененного списка, поэтому возвращаемое значение

     этого узла должен быть назначен * /

    Node pairWiseSwap(Node node)

    {

  

        // Базовый случай: список пуст или имеет только один узел

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

            return node;

        }

  

        // Сохранить заголовок списка после двух узлов

        Node remaing = node.next.next;

  

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

        Node newhead = node.next;

  

        // Изменить следующий из второго узла

        node.next.next = node;

  

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

        node.next = pairWiseSwap(remaing);

  

        // Возвращаем новую голову изменённого списка

        return newhead;

    }

  

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

    void printList(Node node)

    {

        while (node != null) {

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

            node = node.next;

        }

    }

  

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

    public static void main(String[] args)

    {

  

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

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

        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 pairwiseSwap() ");

        list.printList(head);

        head = list.pairWiseSwap(head);

        System.out.println("");

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

        list.printList(head);

        System.out.println("");

    }

}

C #

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

using System;

  

public class LinkedList {

    Node head;

  

    class Node {

        public int data;

        public Node next;

  

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    / * Функция для парного обмена

        элементы связанного списка.

        Возвращает голову модифицированного

        список, поэтому возвращаем значение этого

        узел должен быть назначен * /

    Node pairWiseSwap(Node node)

    {

  

        // Базовый случай: список пуст

        // или имеет только один узел

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

            return node;

        }

  

        // Сохранить заголовок списка после двух узлов

        Node remaing = node.next.next;

  

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

        Node newhead = node.next;

  

        // Изменить следующий из второго узла

        node.next.next = node;

  

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

        // и меняем следующую голову

        node.next = pairWiseSwap(remaing);

  

        // Возвращаем новую голову изменённого списка

        return newhead;

    }

  

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

    void printList(Node node)

    {

        while (node != null) {

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

            node = node.next;

        }

    }

  

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

    public static void Main()

    {

  

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

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

        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 pairwiseSwap() ");

        list.printList(list.head);

        list.head = list.pairWiseSwap(list.head);

        Console.WriteLine("");

        Console.WriteLine("Linked list after calling pairwiseSwap() ");

        list.printList(list.head);

        Console.WriteLine("");

    }

}

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


Выход:

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

Попарно поменяйте местами соседние узлы связанного списка, изменив указатели | Набор 2

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

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

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

0.00 (0%) 0 votes