迹忆客 专注技术分享

当前位置:主页 > 学无止境 > 算法 >

链表反转

作者:迹忆客 最近更新:2023/03/26 浏览次数:

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

  • 数据项。
  • 下一个节点的地址。
class Node
{
    int data;
    Node *next;
};

链表

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

链表反转算法

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

迭代算法

  • 初始化 3 个指针-curr 设置为 headprevnext 设置为 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 以指向头部,即节点 2prev 以及 curr 的数据为 NULL
  • next 指向 curr->next,其值等于 4
  • curr->next 设置为 prev,以获得以 2 为首的反向链接列表。
  • prev 移至 curr,即数据为 2 的节点,将 curr 移至 next,即数据为 4 的节点
  • next 指向 curr->next,其值等于 6
  • curr->next 设置为 prev,以获得以 24 为反向节点,以 4 为首的反向链表。
  • prev 移至 curr,即数据为 4 的节点,将 curr 移至 next,即数据为 6 的节点。
  • next 指向 curr->next,其值等于 8
  • curr->next 设置为 prev,以获得以 246 为反向节点且以 6 为首的反向链表。
  • prev 移至 curr,即数据为 6 的节点,将 curr 移至 next,即数据为 8 的节点。
  • next 指向 curr->next,即 NULL
  • curr->next 设置为 prev,以 2468 作为反向节点,以 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),因为除了临时指针外,不需要额外的空间。

上一篇:链表插入

下一篇:链表删除

转载请发邮件至 1244347461@qq.com 进行申请,经作者同意之后,转载请以链接形式注明出处

本文地址:

相关文章

将二叉树转换为二叉搜索树

发布时间:2023/03/20 浏览次数:159 分类:算法

本教程教大家如何将二叉树转换为二叉搜索树。二叉树是一种非线性数据结构。它被称为二叉树,因为每个节点最多有两个子节点。这些子节点被称为左子和右子。

二叉搜索树删除

发布时间:2023/03/20 浏览次数:164 分类:算法

本教程介绍了二叉搜索树的删除操作。

二叉搜索树检查

发布时间:2023/03/20 浏览次数:151 分类:算法

如何检查给定的二叉树是否是二叉搜索树。

二叉搜索树

发布时间:2023/03/20 浏览次数:105 分类:算法

本教程介绍了数据结构 Binary Search Tree。

二叉树遍历

发布时间:2023/03/20 浏览次数:202 分类:算法

本教程介绍了二叉树上的树遍历中序遍历、前序遍历和后序遍历。

循环双向链表

发布时间:2023/03/20 浏览次数:143 分类:算法

本教程介绍了循环双向链表的数据结构。

循环链接列表

发布时间:2023/03/20 浏览次数:188 分类:算法

本教程介绍了循环链接列表的数据结构。

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

最新推荐

教程更新

热门标签

扫码一下
查看教程更方便