迹忆客 专注技术分享

链表是线性数据结构。链表的一个节点包括：

• 数据项。
• 下一个节点的地址。

class Node
{
    int data;
    Node *next;
};

本文将介绍如何在给定指向链表头节点的指针的情况下反转链表。

链表反转算法

令 head 成为链接列表的第一个节点。

迭代算法

• 初始化 3 个指针-curr 设置为 head，prev 和 next 设置为 NULL。
• 遍历链接列表，直到到达最后一个节点，即 curr！=NULL 并执行以下操作：
  • 将 next 设置为 curr->next 个，以将 next 移动到其下一个节点。
  • 通过将当前节点指向 prev 来反转其方向。因此，将 curr->next 设置为 prev。
  • 将 prev 设置为 curr，将其向前移动一个位置。
  • 将 curr 设置为 next，将其向前移动一个位置。

递归算法

• 将列表分为两部分：第一个节点，即 head 节点，以及其余的链接列表。
• 调用 reverse(head->next)，即，反向链接列表的其余部分，并将反向链接列表存储为 rev。
• 将 head 附加到反向链接列表 rev 的末尾。
• 指向 head，即反向链接列表的尾部指向 NULL

使用堆栈的反向链接列表

• 初始化指向链接列表的 head 的指针 curr。
• 遍历链表，并将每个节点一一插入。
• 将 head 更新到链表中的最后一个节点，即堆栈中的第一个节点。
• 开始一个接一个地从堆栈中弹出节点，并将其附加到反向链表的末尾。
• 将最后一个节点的下一个指针更新为 NULL。

链表反转图解

• 初始化 curr 以指向头部，即节点 2 和 prev 以及 curr 的数据为 NULL。
• 将 next 指向 curr->next，其值等于 4。
• 将 curr->next 设置为 prev，以获得以 2 为首的反向链接列表。
• 将 prev 移至 curr，即数据为 2 的节点，将 curr 移至 next，即数据为 4 的节点
• 将 next 指向 curr->next，其值等于 6
• 将 curr->next 设置为 prev，以获得以 2 和 4 为反向节点，以 4 为首的反向链表。
• 将 prev 移至 curr，即数据为 4 的节点，将 curr 移至 next，即数据为 6 的节点。
• 将 next 指向 curr->next，其值等于 8。
• 将 curr->next 设置为 prev，以获得以 2，4 和 6 为反向节点且以 6 为首的反向链表。
• 将 prev 移至 curr，即数据为 6 的节点，将 curr 移至 next，即数据为 8 的节点。
• 将 next 指向 curr->next，即 NULL。
• 将 curr->next 设置为 prev，以 2，4，6 和 8 作为反向节点，以 8 作为头获得反向链表。
• 将 prev 移至 curr，即数据为 8 的节点，将 curr 移至 NULL，算法终止。

链表反转的实现

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int x) {
        this->data = x;
        this->next = NULL;
    }
};

void printList(Node* head)
{
    Node*curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
}

Node* reverse(Node* head)
{

    Node* curr = head;
    Node *prev = NULL, *next = NULL;

    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
    return head;
}

Node* recursiveReverse(Node* head)
{
    if (head == NULL || head->next == NULL)
        return head;

    Node* rest = recursiveReverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return rest;
}

void reverseLL(Node** head)
{

    stack<Node*> s;
    Node* temp = *head;
    while (temp->next != NULL)
    {
        s.push(temp);
        temp = temp->next;
    }
    *head = temp;

    while (!s.empty())
    {
        temp->next = s.top();
        s.pop();
        temp = temp->next;
    }
    temp->next = NULL;
}

int main()
{
    Node* head = new Node(1);
    head -> next = new Node(2);
    head -> next-> next = new Node(3);
    head -> next-> next-> next = new Node(4);
    head -> next-> next-> next-> next = new Node(5);
    head -> next-> next-> next-> next-> next = new Node(6);
    head = reverse(head);
    printList(head); cout << "\n";
    head = recursiveReverse(head);
    printList(head); cout << "\n";
    reverseLL(&head);
    printList(head); cout << "\n";
    return 0;
}

链表反转算法复杂度

时间复杂度

• 平均情况

要反转完整的链表，我们必须访问每个节点，然后将其附加到反转表。因此，如果一个链表具有 n 个节点，则遍历的平均情况下时间复杂度约为 O(n)。时间复杂度约为 O(n)。

• 最佳情况

最佳情况下的时间复杂度是 O(n)。它与平均情况下的时间复杂度相同。

• 最坏情况

最差的时间复杂度是 O(n)。它与最佳情况下的时间复杂度相同。

空间复杂度

该遍历算法的空间复杂度为 O(1)，因为除了临时指针外，不需要额外的空间。