链表反转-ag捕鱼王app官网

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

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

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 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)，因为除了临时指针外，不需要额外的空间。