AI 助理
文档备案控制台
开发者社区 开发与运维 文章 正文

数据结构单链表之反转链表 | 第九套

2023-11-27 304
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构单链表之反转链表 | 第九套

给定指向链表头节点的指针，任务是反转链表。我们需要通过改变节点之间的链接来反转列表。

例子：

输入：以下链表的头部

1->2->3->4->NULL

输出：链表应改为，

4->3->2->1->NULL

输入：以下链表的头部

1->2->3->4->5->NULL

输出：链表应改为，

5->4->3->2->1->NULL

输入：NULL

输出：NULL输入：1->NULL

输出：1->NULL


  • 将三个指针 prev 初始化为 NULL，curr 为 head，next 为 NULL。
  • 遍历链表。 在循环中，执行以下操作。
    // 在改变当前的下一个之前，存储下一个节点
    next = curr->next
    // 现在更改当前的下一个这是实际发生逆转的地方
    curr->next = prev
    // 将 prev 和 curr 向前移动一步 prev = curr
    curr = next


b4687229ef064a69bd194f753220e7ce_tplv-k3u1fbpfcp-zoom-in-crop-mark_1512_0_0_0.gif

#include <iostream>
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; }
  void reverse()
  {
    Node* current = head;
    Node *prev = NULL, *next = NULL;
    while (current != NULL) {
      next = current->next;
      current->next = prev;
      prev = current;
      current = next;
    }
    head = prev;
  }
  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(20);
  ll.push(4);
  ll.push(15);
  ll.push(85);
  cout << "Given linked list\n";
  ll.print();
  ll.reverse();
  cout << "\nReversed Linked list \n";
  ll.print();
  return 0;
}

输出：

Given linked list
85 15 4 20 
Reversed Linked list 
20 4 15 85


时间复杂度：  O(n)

空间复杂度：  O(1)

递归方法： 

   1）将列表分为两部分 - 第一个节点和
      链表的其余部分。
   2) 对链表的其余部分调用 reverse。
   3）将休息链接到第一个。
   4) 修复头部指针

#include <iostream>
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;
    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(20);
  ll.push(4);
  ll.push(15);
  ll.push(85);
  cout << "Given linked list\n";
  ll.print();
  ll.head = ll.reverse(ll.head);
  cout << "\nReversed Linked list \n";
  ll.print();
  return 0;
}

输出：

Given linked list
85 15 4 20 
Reversed Linked list
20 4 15 85

时间复杂度：  O(n)

空间复杂度：  O(1)

一种更简单的尾递归方法

下面是这个方法的实现。

#include <bits/stdc++.h>
using namespace std;
struct Node {
  int data;
  struct Node* next;
};
void reverseUtil(Node* curr, Node* prev, Node** head);
void reverse(Node** head)
{
  if (!head)
    return;
  reverseUtil(*head, NULL, head);
}
void reverseUtil(Node* curr, Node* prev, Node** head)
{
  if (!curr->next) {
    *head = curr;
    curr->next = prev;
    return;
  }
  Node* next = curr->next;
  curr->next = prev;
  reverseUtil(next, curr, head);
}
Node* newNode(int key)
{
  Node* temp = new Node;
  temp->data = key;
  temp->next = NULL;
  return temp;
}
void printlist(Node* head)
{
  while (head != NULL) {
    cout << head->data << " ";
    head = head->next;
  }
  cout << endl;
}
int main()
{
  Node* head1 = newNode(1);
  head1->next = newNode(2);
  head1->next->next = newNode(3);
  head1->next->next->next = newNode(4);
  head1->next->next->next->next = newNode(5);
  head1->next->next->next->next->next = newNode(6);
  head1->next->next->next->next->next->next = newNode(7);
  head1->next->next->next->next->next->next->next
    = newNode(8);
  cout << "Given linked list\n";
  printlist(head1);
  reverse(&head1);
  cout << "\nReversed linked list\n";
  printlist(head1);
  return 0;
}

输出

Given linked list
1 2 3 4 5 6 7 8 
Reversed linked list
8 7 6 5 4 3 2 1

使用堆栈：

  • 将节点（值和地址）存储在堆栈中，直到输入所有值。
  • 完成所有条目后，将 Head 指针更新到最后一个位置（即最后一个值）。
  • 开始弹出节点（值和地址）并以相同的顺序存储它们，直到堆栈为空。
  • 将堆栈中最后一个 Node 的 next 指针更新为 NULL。

下面是上述方法的实现：


#include <bits/stdc++.h>
#include <iostream>
using namespace std;
class Node
{
public:
  int data;
  Node* next;
};
void reverseLL(Node** head)
{
  stack<Node*> s;
  Node* temp = *head;
  while (temp->next != NULL)
  {
    // Push all the nodes
    // in to stack
    s.push(temp);
    temp = temp->next;
  }
  *head = temp;
  while (!s.empty())
  {
    temp->next = s.top();
    s.pop();
    temp = temp->next;
  }
  temp->next = NULL;
}
void printlist(Node* temp)
{
  while (temp != NULL)
  {
    cout << temp->data << " ";
    temp = temp->next;
  }
}
void insert_back(Node** head, int value)
{
  Node* temp = new Node();
  temp->data = value;
  temp->next = NULL;
  if (*head == NULL)
  {
  *head = temp;
  return;
  }
  else
  {
  Node* last_node = *head;
  while (last_node->next != NULL)
  {
    last_node = last_node->next;
  }
  last_node->next = temp;
  return;
  }
}
int main()
{
  Node* head = NULL;
  insert_back(&head, 1);
  insert_back(&head, 2);
  insert_back(&head, 3);
  insert_back(&head, 4);
  cout << "Given linked list\n";
  printlist(head);
  reverseLL(&head);
  cout << "\nReversed linked list\n";
  printlist(head);
  return 0;
}
**输出**
```C++
Given linked list
1 2 3 4 
Reversed linked list
4 3 2 1

使用数组：

1. 创建一个链表。

2. 然后，做一个count(head)函数来统计节点数。

3. 用计数的大小初始化一个数组。

4. 并开始一个while(p->next!=NULL)循环并将所有节点的数据存储到数组中。

5. 然后将数组从最后一个索引打印到第一个。

#include <iostream>
#include<cstdlib>
using namespace std;
typedef struct node
{
int val;
struct node* next;
}node;
node* head=NULL;
int count(node* head) 
{
node* p=head;
int k=1;
while(p!=NULL)
{
  p=p->next;
  k++;
}
return k;
}
node *ll_reverse(node* head) 
{
node* p=head;
long int i=count(head),j=1;
long int arr[i];
while(i && p!=NULL)
{
  arr[j++]=p->val;
  p=p->next;
  i--;
}
j--;
while(j) 
{
  cout<<arr[j--]<<" ";
}
return head;
}
node* insert_end(node* head,int data) 
{
node* q=head,*p=(node*)malloc(sizeof(node));
p->val=data;
while(q->next!=NULL)
{
  q=q->next;
}
q->next=p;
p->next=NULL;
return head;
}
node *create_ll(node* head,int data) 
{
node* p=(node*)malloc(sizeof(node));
p->val=data;
if(head==NULL)
{
  head=p;
  p->next=NULL;
  return head;
}
else
{
  head=insert_end(head,data);
  return head;
}
}
int main()
{
int i=5,j=1;
while(i--)
{
  head=create_ll(head,j++);
}
head=ll_reverse(head);
  return 0;
}

输入：1->2->3->4->5
输出：5->4->3->2->1

时间复杂度：O(n) 空间复杂度：O(n)

文章标签：
存储
索引
海拥
目录
相关文章
LucianaiB
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
LucianaiB
403 4
Cyan_RA9
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表（下）
408考研——《数据结构》算法题基础篇之链表（下）。
Cyan_RA9
696 30
Cyan_RA9
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表（上）
408考研——《数据结构》算法题基础篇之链表（上）。
Cyan_RA9
991 25
RossyYan
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】
本内容介绍了单链表的基本运算任务，涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法，并提供了测试说明、通 - **任务描述**：实现单链表的基本运算。 - **相关知识**：包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**：平台会对你编写的代码进行测试，提供测试输入和预期输出。 - **通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了测试通过后的预期输出结果。 开始你的任务吧，祝你成功！
RossyYan
775 5
java冯坚持
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
431 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
三三是该溜子
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
482 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
龙大吉
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
638 5
ephemerals__
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
1880 4
盛透侧视攻城狮
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
盛透侧视攻城狮
386 2
盛透侧视攻城狮
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
盛透侧视攻城狮
380 2

热门文章

最新文章

  • 1
    【数据结构入门】-堆的实现以及堆排序（2）
  • 2
    [数据结构] 数组与链表的优缺点和区别
  • 3
    栈
  • 4
    数据结构和算法常见面试问题总结，含答案
  • 5
    每周一道数据结构（二）排序总结
  • 6
    数据结构与算法之美 | 数据结构中到底有多少种“树”？一文告诉你
  • 7
    数据结构中平衡二叉树插入删除中左旋、右旋、左右双旋、右左双旋的详解（题目讲解 简单易懂）
  • 8
    Java数据结构与算法(五)-双向链表
  • 9
    数据结构基础(14) --链式队列的设计与实现
  • 10
    数据结构与算法——链表
  • 1
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
    808
  • 2
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
    716
  • 3
    Redis数据结构：别小看这5把“瑞士军刀”，用好了性能飙升！
    811
  • 4
    软考中级软件设计师专项-数据结构与算法上篇
    989
  • 5
    【Redis】常用数据结构之List篇：从常用命令到典型使用场景
    858
  • 6
    Redis基础命令与数据结构概览
    373
  • 7
    Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
    561
  • 8
    【Redis】 常用数据结构之String篇：从SET/GET到INCR的超全教程
    925
  • 9
    【📕分布式锁通关指南 12】源码剖析redisson如何利用Redis数据结构实现Semaphore和CountDownLatch
    891
  • 10
    Redis核心数据结构与分布式锁实现详解
    1236

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    一条命令迁移，帮你实现 OpenClaw 与 Hermes Agent 记忆互通！