Поміняйте місцями вузли у рішеннях Leetcode пар


Рівень складності Medium
Часто запитують у Амазонка Apple Bloomberg Facebook Microsoft
Зв’язаний список

Метою цієї проблеми є обмін вузлами даної пов'язаний список попарно, тобто міняючи місцями кожні два сусідні вузли. Якщо нам дозволено поміняти місцями лише значення вузлів списку, проблема буде тривіальною. Отже, нам не дозволено змінювати значення вузлів.

Приклад

1 2 3 4
2 1 4 3
6 7 3
7 6 3

Підхід

Ми можемо помітити, що ми можемо поміняти місцями два вузли в парі. Обмін тут означає маніпулювати покажчиками так, щоб перший вузол був підключений до решти пов'язаного списку, а другий вузол тепер стає голова вказуючи на перший вузол.

Поміняти місцями вузли списку парами Leetcode Solutions

Список, що залишився після цього обміну, тепер стає підзадачею того, що було початковою проблемою. Отже, ми можемо викликати ту саму рекурсивну функцію до решти списку. Тут ми повинні відстежувати, що голова списку є фактично другим вузлом у списку. Це достатнє рішення, але займає простір, оскільки рекурсія створює кадри стека в пам'яті.

Оптимальний метод можна легко розглянути як подібний підхід, реалізований ітеративно. Для цього нам потрібно створити попередній вузол, який буде зберігати хвіст лише попередньої пари, яку ми поміняли місцями. Помінявши місцями вузли поточної пари, ми з'єднуємо хвіст попередньої пари з головою цієї пари.

Алгоритм (рекурсивний підхід)

  1. Прості базові умови - це коли навіть немає двох вузлів для формування пари. В такому разі:
    • Список може бути NULL або може містити один предмет.
    • Поверніть його як є.
  2. Тепер, коли у нас є пара, використовуйте перший і другий для позначення першого та другого предметів нашої пари.
  3. З перший вузол став би хвостом цієї пари,
    1. викликати рекурсивну функцію, починаючи з наступної пари (вузол після другий).
    2. Підзадача вирішується функцією та додається до неї перший вузол.
    3. Тепер додайте перший вузол, який також має відпочинок списку, підключеного до нього, до другого вузла.
  4. Оскільки ми хочемо другий вузол для обміну перша секунда стане головою зараз,
    1. Повертати другий

Алгоритм (оптимальний)

  1. Створити попередній покажчик, що вказує на якийсь фіктивний вузол, підтримуйте його прехед.
  2. Установка наступний попереднього вузла як поточний заголовок списку.
  3. Цей попередній вказівник може вказувати на наступну замінену пару.
  4. Якщо список є NULL або має лише один елемент
    • повернути список
  5. Продовжуйте повторювати, поки не дійдемо до точки, де список закінчується або залишився лише один вузол:
    • Збережіть адресу наступної пари в температура змінна.
    • Поміняйте місцями два вузли цієї пари: перший вузол і другий вузол
    • Підключіть prevNode до другого вузла цієї пари
    • Оновіть попередній вузол як перший вузол (оскільки він зараз стане хвостом)
    • Оновіть head = temp, щоб ми могли стрибати до наступної пари
  6. Список все ще може бути NULL або може залишитися один елемент, тому підключіть prevNode до решти списку.
  7. поверніть dummy.next, щоб отримати необхідний список.

Реалізація

Програма C ++ для обміну вузлами в парах рішення Леткод

Рекурсивний підхід

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};


void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}

listNode* swapNodesInPairs(listNode* head)
{
    if(head == NULL || head->next == NULL)
        return head;

    listNode* first = head , *second = head->next;
    first->next = swapNodesInPairs(head->next->next);

    second->next = first;
    return second;
}



int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);

    print(swapNodesInPairs(head));
    return 0;
}

Ітераційний підхід

#include <bits/stdc++.h>
using namespace std;
struct listNode
{
    int value;
    listNode* next;
    listNode(int x)
    {
        value = x;
        next = NULL;
    }
};


void print(listNode* head)
{
    while(head)
    {
        cout << head->value << " ";
        head = head->next;
    }
    cout << '\n';
    return;
}


listNode* swapNodesInPairs(listNode* head)
{
    if(head == NULL || head->next == NULL)
        return head;

    //initialise the prevNode
    listNode *prevNode = new listNode(-1) , *prehead = prevNode;
    prevNode->next = head;


    listNode *first , *second , *temp;
    //temporary variable to store first and second of every pair

    while(head != NULL && head->next != NULL)
    {
        first = head;
        second = head->next;

        temp = second->next;
        second->next = first;
        prevNode->next = second;
        //connecting previous node to the second of this pair


        prevNode = first;
        head = temp;
        //reinitialising previous node and head for next pair
    }

    prevNode->next = head;
    return prehead->next;
}


int main()
{
    listNode* head = new listNode(1);
    head->next = new listNode(2);
    head->next->next = new listNode(3);

    print(swapNodesInPairs(head));
    return 0;
}
2 1 3

Програма Java для обміну вузлами парами рішень з використанням Лет-коду

Рекурсивний підхід

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class swap_nodes_in_pairs
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }

    public static listNode swapNodesInPairs(listNode head)
    {
        if(head == null || head.next == null)
            return head;

        listNode first = head , second = head.next;

        first.next = swapNodesInPairs(head.next.next);
        second.next = first;

        return second;
    }

    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(4);

        print(swapNodesInPairs(head));
    }
}

Ітераційний підхід

class listNode
{
    int value;
    listNode next;

    listNode(int x)
    {
        value = x;
        next = null;
    }
}

class swap_nodes_in_pairs
{
    public static void print(listNode head)
    {
        while(head != null)
        {
            System.out.print(head.value + " ");
            head = head.next;
        }
        return;
    }

    public static listNode swapNodesInPairs(listNode head)
    {
        if(head == null || head.next == null)
            return head;

        //initialise the prevNode
        listNode prevNode = new listNode(-1) , prehead = prevNode;
        prevNode.next = head;


        listNode first , second , temp;
        //temporary variable to store first and second of every pair

        while(head != null && head.next != null)
        {
            first = head;
            second = head.next;

            temp = second.next;
            second.next = first;
            prevNode.next = second;
            //connecting previous node to the second of this pair


            prevNode = first;
            head = temp;
            //reinitialising previous node and head for next pair
        }

        prevNode.next = head;
        return prehead.next;
    }

    public static void main(String args[])
    {
        listNode head = new listNode(1);
        head.next = new listNode(2);
        head.next.next = new listNode(3);
        head.next.next.next = new listNode(4);

        print(swapNodesInPairs(head));
    }
}
2 1 4 3

Аналіз складності

Складність часу поміняти місцями вузли попарно

Рекурсивний підхід: O (N), оскільки ми робимо лише один прохід у списку. Ітераційний підхід: O (N), знову робимо один прохід.

Складність простору поміняти місцями вузли попарно

Рекурсивний підхід: O (N), оскільки рекурсія створює стекові кадри для кожного виклику в пам'яті. Ітераційний підхід: O (1), оскільки постійний простір використовується для деяких змінних. Тут ітераційний підхід краще.