Учебник: как развернуть связанный список в C++?

Знание того, как работать с языком программирования C ++, делает вас конкурентоспособным кандидатом на различные должности. По мере того, как вы переходите к новым ролям, вы будете проходить собеседования, которые проверят ваше понимание основ информатики, таких как структуры данных и алгоритмы. Связанный список — это лишь одна из многих структур данных C ++, которые вам нужно знать при собеседовании. Один из популярных вопросов на собеседовании — перевернуть связанный список.

Сегодня мы рассмотрим руководство по обращению односвязных списков в C ++. Мы продемонстрируем итеративное и рекурсивное решение этой проблемы.

Связанные списки

Связанные списки — это линейные структуры данных, соединяющие узлы в последовательности. Каждый узел состоит из двух компонентов: 1.) элемента данных и 2.) указателя, содержащего адрес памяти на следующий узел в списке.

В случае односвязного списка узлы хранят только один указатель на следующий узел в последовательности. С другой стороны, узел в двусвязном списке хранит два указателя : один на следующий узел и один на предыдущий узел в последовательности. Односвязный список является однонаправленным, а двусвязный список двунаправленным. В случае односвязного списка указатель хвостового узла равен нулю.

Некоторые термины, связанные со связанными списками:

• Node: объект в списке с двумя компонентами: фрагментом данных (элементом) и указателем.
• Next: следующий узел в последовательности, соответствующий данному узлу списка.
• Head: первый узел в связанном списке.
• Tail: последний узел в связанном списке называется хвостом.
• Head pointer: адрес памяти, содержащийся в головном узле, ссылающийся на первый узел в списке.

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

Описание проблемы: реверсирование связанного списка

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

Например, при наличии данного связанного списка:

Обратно связанный список будет выглядеть так:

Решение 1.Инвертируйте связанный список с помощью итерации

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

Мы определим три узла : текущий (со ссылкой на головной узел), а также временный и предыдущий (с нулевыми указателями). Используя цикл while, мы просматриваем связанный список до тех пор, пока следующий указатель не перестанет работать null.

В итеративном процессе мы выполним следующие операции:

• temp = current->next;
  • Назначает временный узел следующему узлу текущего узла
• current->next = prev;
  • Назначает текущий узел следующему узлу предыдущего узла
• prev = current;
  • Увеличивает предыдущий узел до текущего узла
• current = temp;
  • Увеличивает текущий узел до временного узла

Затем мы возвращаем головной узел перевернутого списка.

#include<bits/stdc++.h>

using namespace std;

struct node {

    int data;

    struct node *next;

};

// We construct a linked list and use this function to push elements to the list

void push(struct node **head_ref, int data) {

    struct node *node;

    node = (struct node*)malloc(sizeof(struct node));

    node->data = data;

    node->next = (*head_ref);

    (*head_ref) = node;

}

// Function to reverse the list

void reverse(struct node **head_ref) {

    struct node *temp = NULL;

    struct node *prev = NULL;

    struct node *current = (*head_ref);

    while(current != NULL) {

        temp = current->next;

        current->next = prev;

        prev = current;

        current = temp;

    }

    (*head_ref) = prev;

}

// Checking our program

void printnodes(struct node *head) {

    while(head != NULL) {

        cout<<head->data<<» «;

        head = head->next;

    }

}

// Driver function

int main() {

    struct node *head = NULL;

    push(&head, 28);

    push(&head, 21);

    push(&head, 14);

    push(&head, 7);

    cout << «Original Linked List» << endl;

    printnodes(head);

    reverse(&head);

    cout << endl;

    cout << «Reversed Linked List»<<endl;

    printnodes(head);

    return 0;

}

O (N) — это временная сложность этого решения, поскольку мы повторяем каждый элемент как минимум один раз. O (1) — это сложность пространства, потому что для решения не требовалось дополнительной памяти.

Решение 2. Инвертируйте связанный список с помощью рекурсии

Рекурсивное решение использует стек. Каждый рекурсивный вызов требует, чтобы ваш компилятор выделял стековую память. Поскольку в рекурсивной реализации может не хватить памяти, рекурсивное решение — не лучший подход при работе с очень большими связными списками.

Чтобы вернуть заголовок нового списка, мы рекурсивно посещаем каждый узел в данном связанном списке, пока не дойдем до последнего узла. Этот последний узел затем служит новым заголовком списка. На пути возврата каждый узел добавляется в конец частично перевернутого списка.

#include<bits/stdc++.h>

using namespace std;

struct Node {

    int data;

    struct Node* next;

    Node(int data)

    {

        this->data = data;

        next = NULL;

    }

};

struct LinkedList {

    Node* head;

    LinkedList()

    {

        head = NULL;

    }

    Node* reverse(Node* head)

    {

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

            return head;

        // Recursive call

        Node* rest = reverse(head->next);

        head->next->next = head;

        head->next = NULL;

        return rest;

    }

    void print()

    {

        struct Node* temp = head;

        while (temp != NULL) {

            cout << temp->data << » «;

            temp = temp->next;

        }

    }

    void push(int data)

    {

        Node* temp = new Node(data);

        temp->next = head;

        head = temp;

    }

};

int main()

{

    LinkedList ll;

    ll.push(28);

    ll.push(21);

    ll.push(14);

    ll.push(7);

    cout << «Original Linked List\n»;

    ll.print();

    ll.head = ll.reverse(ll.head);

    cout << «\nReversed Linked List \n»;

    ll.print();

    return 0;

}

Пространство сложность этого решения является O (N), так как мы создаем рекурсивный стек для каждого вызова рекурсивной функции. O (N) — это временная сложность этого решения, поскольку мы повторяем каждый элемент как минимум один раз.