首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
人狠话不多的六边形战士很想去东北泡澡
西安电子科技大学 电子信息类
发布于北京
关注
已关注
取消关注
@开车的阿Q:
题解 | #反转链表#
描述 这是一篇面对初级coder的题解。 知识点:链表 栈 难度:一星 题解 题目:输入一个链表,反转链表后,输出新链表的表头。 考察链表的基础知识 方法一:栈 利用栈后进先出的特性,可以实现链表翻转 #includeclass Solution {public: ListNode* ReverseList(ListNode* pHead) { stack<listnode> stack;//栈 ListNode *answer=NULL;//返回值 if(!pHead) return pHead; while(pHead->next)//全部入栈 { stack.push(pHead); pHead=pHead->next; } answer = pHead; for(int k=stack.size(); k>0;k--) { pHead->next=stack.top(); stack.pop(); pHead=pHead->next; } pHead->next = nullptr;//尾指针置空 避免回环 return answer; }};</listnode> 运行时间 6ms 占用内存 504KB 方法二:用指针调转 本质上是两个链表,逐个把旧链表的节点调转到新链表下 一个复杂且清晰的版本 class Solution {public: ListNode* ReverseList(ListNode* pHead) { struct ListNode *newnode=NULL; //新节点 struct ListNode *tempnode;//交换缓存 if(pHead==NULL) return pHead; while(pHead->next!=NULL) { if(newnode == NULL)//第一次进入 { newnode = pHead;//把头结点挪过来 pHead=pHead->next; newnode->next=NULL; } else { tempnode=newnode;//利用交换缓存从旧链表取节点,作为新链表头节点 newnode=pHead; pHead=pHead->next; newnode->next=tempnode; } } pHead->next=newnode;//把最后一个节点挂上去 return pHead; }}; 运行时间 8ms 占用内存 624KB 进一步优化代码逻辑 class Solution {public: ListNode* ReverseList(ListNode* pHead) { struct ListNode *newnode=NULL; //新链表头指针 struct ListNode *tempnode;//交换缓存,临时存放要换过来的头节点 while(pHead) { tempnode=pHead->next;//利用交换缓存从旧链表取节点, pHead->next=newnode;//作为新链表头节点 newnode=pHead;//更新新链表 pHead=tempnode;//更新旧链表 } return newnode;//返回新链表 }}; 运行时间 8ms 占用内存 632KB 总结 各位牛友在练习的时候要注意边界条件的判定 扩展 快慢指针是链表中一种常见的处理方法 在判断链表中是否有环中也很有用
点赞 6
评论 1
全部评论
推荐
最新
楼层
秋招专场
校招火热招聘中
官网直投
相关推荐
DDDDDOS
05-31 00:05
门头沟学院 材料类
暑期总结:充满运气的马拉松
偶然发现力扣的做题记录很好地反映了这几个月的精神状态近日暑期终于接近尾声,过程中从牛客获益良多;所以也来分享一点心得,算作为后来人栽树==========================个人情况:防盒不细讲,9本华五硕,本科一段水实习,项目经历写的横向投递岗位:java后端==========================准备过程:很久以前陆续看一些《面试小抄》(后来发现实则为javaguide),这个东西快速复习用很好但是有些章节太浮于表面,不建议作为学习的唯一课本黑马的b站经典redis课程,黑马点评。神中神,我觉得是调整学习状态的第一步,起码我个人是从redis开始被引入向性能...
投递快手等公司10个岗位 >
我的实习日记
找实习多的是你不知道的事
点赞
评论
收藏
转发
你今天学到了啥
06-01 15:26
已编辑
重庆大学 计算机类
暑期实习简历被挂麻了,佬们看看啥问题
点赞
评论
收藏
转发
土豆小魔王
04-27 01:29
已编辑
香港大学 计算机类
记录一下失败的找实习记录
累了华为:一面挂,面试官问我GPA和排名,我说不出来😭小米 sre工程师/cpp客户端:简历挂特斯拉 cpp客户端:简历挂4399 游戏客户端开发:笔试挂腾讯 pcg桌面cpp开发:一面挂普联:没消息百度:学姐给内推,好像没hc了直接发的拒信快手 cpp:简历挂oppo:一面被华为顶掉了,挂中行:没消息交行:没消息完美世界 游戏策划/客户端:没消息联想 python开发 没消息比亚迪 没消息埃森哲 没消息
投递4399游戏等公司10个岗位
点赞
评论
收藏
转发
刷了100道题的无尾熊很讲文明
05-31 23:28
北京理工大学 电子信息类
25届都还有谁在找实习
25届都还有谁在找实习??双9基本颗粒无收,准备看中小厂机会了
我的实习求职记录
正在实习的碎碎念
点赞
评论
收藏
转发
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
给你们预测一下今年的秋招!
3104
2
...
海康暑期实习
2674
3
...
【🎁】25届硬件牛牛互助计划(1期)
2656
4
...
阿里体检完还没发正式offer
2638
5
...
深圳蟑螂真的很可怕吗
2337
6
...
拿了蓝桥杯c++b组国二,水平怎么样,找后端开发工作有多大优势?
2211
7
...
毕业了!
1999
8
...
海康威视,25暑期实习,软件开发岗
1838
9
...
5.31拼多多服务端开发实习生一面(75min)
1807
10
...
二本开发转测试,面试成功
1780
正在热议
#
和牛牛一起刷题打卡
#
13738次浏览
1268人参与
#
通信硬件薪资爆料
#
255708次浏览
2409人参与
#
不去互联网可以去金融科技
#
3573次浏览
49人参与
#
牛客帮帮团来啦!有问必答
#
1091982次浏览
16303人参与
#
面试被问第一学历差时该怎么回答
#
18186次浏览
199人参与
#
简历中的项目经历要怎么写?
#
14259次浏览
189人参与
#
工作两年想退休了
#
19229次浏览
239人参与
#
实习生应该准时下班吗
#
93077次浏览
705人参与
#
你收到了团子的OC了吗
#
530574次浏览
6293人参与
#
你已经投递多少份简历了
#
338369次浏览
4905人参与
#
简历无回复,你会继续海投还是优化再投?
#
23445次浏览
329人参与
#
你怎么评价今年的春招?
#
12401次浏览
193人参与
#
简历中的项目经历要怎么写
#
481871次浏览
8758人参与
#
晒一晒我的offer
#
3769265次浏览
58045人参与
#
担心入职之后被发现很菜怎么办
#
39535次浏览
327人参与
#
本周投递记录
#
220842次浏览
5375人参与
#
硬件人的简历怎么写
#
81815次浏览
849人参与
#
我想象的工作vs实际工作
#
105726次浏览
1700人参与
#
2022毕业生求职现身说法
#
23596次浏览
338人参与
#
你的秋招进行到哪一步了
#
396645次浏览
6678人参与
#
产品人求职现状
#
56807次浏览
822人参与
牛客网
牛客企业服务