当前位置:网站首页>C语言快速解决反转链表
C语言快速解决反转链表
2022-07-04 22:35:00 【我不是萧海哇~~~~】
反转链表
题目描述:
给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。
数据范围: 0≤n≤1000
要求:空间复杂度 O(1) ,时间复杂度 O(n)O(n)
如当输入链表{1,2,3}时,经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。
以上转换过程如下图所示:
本文介绍两种方法:
(1)就地反转
(2)双链表法
(感觉两种方法差不多…)
/*struct ListNode { int val; struct ListNode *next; }; */
//用c语言实现
struct ListNode* ReverseList(struct ListNode* pHead ) {
struct ListNode *pre=NULL;//pre指针指向已经反转好的链表的最后一个节点,最开始没有反转,所以指向null
struct ListNode *cur=pHead;//cur指针指向待反转链表的第一个节点,最开始第一个节点待反转,所以指向head
struct ListNode *nex=NULL;//用来保存断链结点,即指针指向待反转链表的第二个节点
while(cur){
nex=cur->next;
cur->next=pre;//实现断链操作
pre=cur;//反转的节点
cur=nex;//指向之前断链的节点
}
return pre;
}
//双链表实现
struct ListNode* ReverseList(struct ListNode* pHead ) {
struct ListNode *newHead=NULL;
while(pHead!=NULL){
struct ListNode *temp=pHead->next; //保存断链结点
pHead->next=newHead;//将新链表挂到访问的原链表节点之后
newHead=pHead;
pHead=temp;
}
return newHead;
}
注:还能使用栈来实现这个题,先进后出输出刚好实现反转
原文:https://blog.csdn.net/qq_46027119/article/details/124182305
边栏推荐
- Google Earth engine (GEE) - globfire daily fire data set based on mcd64a1
- 攻防世界 MISC 进阶区 Erik-Baleog-and-Olaf
- Redis入门完整教程:发布订阅
- Notepad++--编辑的技巧
- A complete tutorial for getting started with redis: transactions and Lua
- 新版判断PC和手机端代码,手机端跳转手机端,PC跳转PC端最新有效代码
- EditPlus--用法--快捷键/配置/背景色/字体大小
- 集群的概述与定义,一看就会
- 攻防世界 MISC 进阶区 can_has_stdio?
- Redis introduction complete tutorial: detailed explanation of ordered collection
猜你喜欢
vim编辑器知识总结
攻防世界 MISC 进阶区 Ditf
Redis getting started complete tutorial: hash description
攻防世界 misc 高手进阶区 a_good_idea
Attack and defense world misc advanced grace-50
Redis的持久化机制
Lost in the lock world of MySQL
Redis入門完整教程:Pipeline
Attack and defense world misc master advanced zone 001 normal_ png
Redis入门完整教程:列表讲解
随机推荐
Redis introduction complete tutorial: detailed explanation of ordered collection
Advanced area a of attack and defense world misc Masters_ good_ idea
云服务器设置ssh密钥登录
剑指Offer 68 - II. 二叉树的最近公共祖先
Mongodb aggregation operation summary
UML diagram memory skills
mamp下缺少pcntl扩展的解决办法,Fatal error: Call to undefined function pcntl_signal()
Unity-VScode-Emmylua配置报错解决
[Lua] Int64 support
UML图记忆技巧
Redis入门完整教程:初识Redis
[odx Studio Edit pdx] - 0.2 - Comment comparer deux fichiers pdx / odx
[machine learning] handwritten digit recognition
Attack and defense world misc advanced zone 2017_ Dating_ in_ Singapore
The solution to the lack of pcntl extension under MAMP, fatal error: call to undefined function pcntl_ signal()
10 schemes to ensure interface data security
PMO: compare the sample efficiency of 25 molecular optimization methods
Detailed explanation of heap sort code
【lua】int64的支持
Attack and defense world misc advanced area ditf