左神算法基础class3—题目7反转单向和双向链表

2023-12-07 19:18

本文主要是介绍左神算法基础class3—题目7反转单向和双向链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

左神算法基础class3—题目7反转单向和双向链表

  • 题目1:反转单向链表
    • 1.分析
    • 2.核心代码
    • 3.完整代码
    • 4.输出结果
  • 题目2:反转双向链表
    • 1.分析
    • 2.核心代码
    • 3.完整代码
    • 4.输出结果

题目1:反转单向链表

【要求】 如果链表长度为N,时间复杂度要求为O(N),额外空间
复杂度要求为O(1)

1.分析

反转单向链表可以使用迭代法,需要三个指针分别记录前一个节点,当前节点和后一个结点。反转时把当前节点指向前一个节点,再把当前节点和前一个节点都后移,继续反转直到末尾。因为反转过后当前节点指向发生变化与之后的节点会断开,所以需要指针来保存当前节点的后一个节点。整体迭代的条件是当前节点不为空。

2.核心代码

(1)生成完整的链表
①数据结构如下,val为数据域,*next指向下一节点,由于指向的是节点,所以需要定义为ListNode型指针。

typedef struct ListNode
{int val;ListNode *next;
}*List;

②使用尾插法:将新加入的节点插入末尾

malloc负责开辟一块空间存储,空间大小是sizeof(ListNode),由于malloc默认返回void*,需要强制转换为List型结构体指针。L为头节点不用于存储数据,只用于存放链表头的地址,将尾节点暂时指向头节点。开辟p节点存储数据,将尾节点指向新的节点构成链表再把新的节点设置为尾节点,继续开辟新结点再存储。最后把尾节点指向空。

	ListNode* L = (List)malloc(sizeof(ListNode));//List L = (List)malloc(sizeof(ListNode));与上式等价L->next = NULL;//使用尾插法List p,r;//p是新结点,r是尾节点r = L;	//把尾节点指向头节点for(int i = 0;i < N;i++){p = (List)malloc(sizeof(ListNode));p->val = i * 5;r->next = p;r = p;}r->next = NULL;

(2)反转单链表

List reverseList(List head) 
{List pre = NULL;List cur = head->next;//需要反转的当前节点从头节点的下一个开始while(cur != NULL){List temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;
}

3.完整代码

#include<iostream>
#include<stdlib.h>
//#include<time.h>
#define N 5
typedef struct ListNode
{int val;ListNode *next;
}*List;List reverseList(List head) 
{List pre = NULL;List cur = head->next;while(cur != NULL){List temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;
}int main()
{//srand(time(0));ListNode* L = (List)malloc(sizeof(ListNode));//List L = (List)malloc(sizeof(ListNode));与上式等价L->next = NULL;//使用尾插法List p,r;//p是新结点,r是尾节点r = L;	//把尾节点指向头节点for(int i = 0;i < N;i++){p = (List)malloc(sizeof(ListNode));//p->val = rand() % 15;p->val = i * 5;r->next = p;r = p;}r->next = NULL;List newhead = NULL;newhead = reverseList(L) ;system("pause");return 0;
}

4.输出结果

L是原来的单向链表,第一个val是头节点;
在这里插入图片描述
反转后的单向链表。
在这里插入图片描述

题目2:反转双向链表

反转单向和双向链表
【题目】 分别实现反转单向链表和反转双向链表的函数。
【要求】 如果链表长度为N,时间复杂度要求为O(N),额外空间
复杂度要求为O(1)

1.分析

双向链表的反转只需要把当前节点的next指针和pre指针交换即可,对每个节点单独操作,不涉及其他节点。

2.核心代码

(1)双向链表的创建
双向链表的数据结构由一个数据域两个指针域构成;


typedef struct doublelist
{int val;doublelist* next;doublelist* pre;}*List;

双向链表的尾插法和单向链表基本相同,只是增加了记录pre指针的步骤;

	List p,r,head = NULL;r = NULL;for(int i = 0;i < 4;i++){p = (List)malloc(sizeof(doublelist));p->val = 5 * i;p->pre = r;if(r == NULL){r = p;head = p;continue;}r->next = p;r = p;}r->next =NULL;

(2)反转双向链表
使用中间变量暂存next指针,再交换next和pre指针,最后把前一个指针指向的结点赋给当前节点,继续进行反转。注意,因为next指针已经和pre指针交换了,所以前一个指针指向的节点实际就是下一个节点。

List reverseList(List head) 
{List p = head;List temp = NULL;while(p!=NULL){temp = p->next;p->next = p->pre;p->pre = temp;p = p->pre;}return head;
}

3.完整代码

#include<iostream>typedef struct doublelist
{int val;doublelist* next;doublelist* pre;}*List;List reverseList(List head) 
{List p = head;List temp = NULL;while(p!=NULL){temp = p->next;p->next = p->pre;p->pre = temp;p = p->pre;}return head;
}int main()
{List p,r,head = NULL;r = NULL;for(int i = 0;i < 4;i++){p = (List)malloc(sizeof(doublelist));p->val = 5 * i;p->pre = r;if(r == NULL){r = p;head = p;continue;}r->next = p;r = p;}r->next =NULL;List newhead = NULL;newhead = reverseList(head) ;return 0;
}

4.输出结果

创建链表时从next方向依次是0,5,10,15,而pre方向是空的;
在这里插入图片描述
反转链表后next方向是空的,而pre方向0,5,10,15,可以看出双向链表已经反转。
在这里插入图片描述

这篇关于左神算法基础class3—题目7反转单向和双向链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/467050

相关文章

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

C++链表的虚拟头节点实现细节及注意事项

《C++链表的虚拟头节点实现细节及注意事项》虚拟头节点是链表操作中极为实用的设计技巧,它通过在链表真实头部前添加一个特殊节点,有效简化边界条件处理,:本文主要介绍C++链表的虚拟头节点实现细节及注... 目录C++链表虚拟头节点(Dummy Head)一、虚拟头节点的本质与核心作用1. 定义2. 核心价值二

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据

Linux链表操作方式

《Linux链表操作方式》:本文主要介绍Linux链表操作方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、链表基础概念与内核链表优势二、内核链表结构与宏解析三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势六、典型应用场景七、调试技巧与

安装centos8设置基础软件仓库时出错的解决方案

《安装centos8设置基础软件仓库时出错的解决方案》:本文主要介绍安装centos8设置基础软件仓库时出错的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录安装Centos8设置基础软件仓库时出错版本 8版本 8.2.200android4版本 javas

Linux基础命令@grep、wc、管道符的使用详解

《Linux基础命令@grep、wc、管道符的使用详解》:本文主要介绍Linux基础命令@grep、wc、管道符的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录grep概念语法作用演示一演示二演示三,带选项 -nwc概念语法作用wc,不带选项-c,统计字节数-

python操作redis基础

《python操作redis基础》Redis(RemoteDictionaryServer)是一个开源的、基于内存的键值对(Key-Value)存储系统,它通常用作数据库、缓存和消息代理,这篇文章... 目录1. Redis 简介2. 前提条件3. 安装 python Redis 客户端库4. 连接到 Re

SpringBoot基础框架详解

《SpringBoot基础框架详解》SpringBoot开发目的是为了简化Spring应用的创建、运行、调试和部署等,使用SpringBoot可以不用或者只需要很少的Spring配置就可以让企业项目快... 目录SpringBoot基础 – 框架介绍1.SpringBoot介绍1.1 概述1.2 核心功能2

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.