牛客--反转链表
创始人
2025-05-30 20:23:44
0次
描述
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围： 0\leq n\leq10000≤n≤1000
要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
输入：{1,2,3}
返回值：{3,2,1}
输入：{}
返回值：{}
说明：空链表则输出空
//代码：
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution
{public:ListNode* ReverseList(ListNode* pHead) {ListNode* pre = nullptr;ListNode* cur = pHead;ListNode* nex =nullptr; // 这里可以指向nullptr，循环里面要重新指向while (cur) {nex = cur->next;cur->next = pre;pre = cur;cur = nex;}return pre;}
};
//理解：
我们要将链表反转，那么最开始的头节点就成了尾节点；
反转前头结点，将其反转，那么它的nex成为它的pre;
pre节点会成为nex节点
要做的事情：
1.找到当前节点的下一个节点，（它成为下一次遍历的当前节点）；
2.当前节点的nex节点是反转前的pre节点；
3.cur节点反转完，成为pre节点
4.cur节点反转完变为1中找到的下一个节点。
链表的当前节点cur,从头开始遍历，
第一次遍历时，它的pre节点是空，它变成后续节点的pre节点，它的nex节点一直为空（反转之后头变尾，尾的nex为nullptr,）；
第二次遍历时，先找下一次要遍历的节点nex，cur节点的nex就是pre,然后确定新的pre 和cur.
相关内容
热门资讯
教师节优美祝福语短信
教师节优美祝福语短信55条 因为有了您，世界才会如此美丽，因为有了您，我的生命才会如此多彩！医生治...
去除Spire.Doc导出字样...
//去除Spire.Doc导出字样信息try (FileInputStream in = n...
给老师的春节贺卡祝福语
给老师的春节贺卡祝福语170句 在我们平凡的日常里，要用到祝福语的情况还是蛮多的，祝福语可以起到增...
父亲节暖心祝福语
父亲节暖心祝福语 在日复一日的学习、工作或生活中，大家都用到过祝福语吧，祝福语有助于促进交流，拉近...
温馨教师节祝福语
2020年温馨教师节祝福语集锦45条 您辛劳了，教师节到了，您也该歇一歇了，坐着接接电话看看短信吧...
《RabbitMQ高阶知识》—...
《RabbitMQ高阶知识》— 消息可靠性 文章目录《RabbitMQ高阶知识》— 消息可靠性&#x...
Kubernetes（5）：P...
我们一般将pod对象从创建至终的这段时间范围称为pod的生命周期，它主要包含下面的过程： pod创建...
学校领导新年元旦祝福语
学校领导新年元旦祝福语校师生员工们： 新年的钟声Ji荡着神州大地，岁月的航船开启着新的征程，我们即...
hugginface相关数据集...
swaption2009/20k-en-zh-translation-pinyin-hsk 翻译 S...
孙子满月酒贺词
孙子满月酒贺词 宝宝降生，我前来贺喜，愿新生的小宝贝给你们带来数不尽的`快乐，祝小宝贝身体健康，茁...
温馨端午节祝福语句
常用温馨端午节祝福语句70句 端午快乐，幸福甜蜜！下文是小编特意为各位读者准备的温馨端午节祝福语句...
SQL常用语法语句
文章目录1. 什么是sql语句？1.1 DDL(数据定义语言)用法2. 什么是数据库对...
暖心重阳节祝福语短信
2020年暖心重阳节祝福语短信大汇总77句 九九重阳节日到，我的短信首先到，登高望远先敬老，赏菊插...
经典七夕祝福语
经典七夕祝福语99句 枯草连天太苍茫，小路白杨一行行。牵手偶因手太凉，曾经一起看夕阳。夕阳挂在柳梢...
感恩老师贺卡祝福语
感恩老师贺卡祝福语（精选270句） 无论是身处学校还是步入社会，大家都写过祝福语，肯定对各类祝福语...
妇女节祝福语QQ
2020年妇女节祝福语QQ大汇总25句 送你杯茶，以芬芳的祝福为叶，温柔的叮嘱做花，用沸腾的热情为...
DINO-DETR 实验与分析
前言 自DETR提出之后，不计其数的DETR改进模型不断被提出，尽管如此...
[图神经网络]图卷积神经网络-...
一、消息传递 由于图具有“变换不变性”(即图的空间结构改变不会影响图的性状)...
开业花篮贺词
开业花篮贺词 在日常学习、工作抑或是生活中，大家对贺词都不陌生吧，贺词要求感情真挚，切合身份，用语...
乔迁之喜祝福语八个字
乔迁之喜祝福语八个字 一、祝福语传递途径 1、在聚会、宴会、烛光餐等庆祝的场合，参与者对主角直接...