C++刷 LeetCode Hot100 笔记（七）链表专题（上）：反转链表、合并两个有序链表、删除链表的倒数第 N 个结点、环形链表、环形链表 II

这一篇开始我们正式进入Hot100 的链表专题。很多人前面数组题刷得还行一到链表就开始晕主要原因不是题太难而是链表不能像数组那样直接下标访问指针一改就容易乱一不小心就断链画面感不强的时候很容易写着写着把自己绕进去所以链表题你不能只靠“感觉写”要学会固定套路。这一篇先带你吃掉 Hot100 链表里最核心、最基础、最常见的 5 道题反转链表合并两个有序链表删除链表的倒数第 N 个结点环形链表环形链表 II这 5 道题特别重要因为它们背后刚好对应链表最常见的几个模型指针反转迭代合并快慢指针判环找环入口1. 先把链表最基本的东西弄清楚在力扣里链表节点一般长这样struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };先别怕这个定义前期你主要看懂两件事就行val当前节点的值next指向下一个节点比如1 - 2 - 3 - nullptr就表示第一个节点值是 1它的next指向值为 2 的节点2 的next指向 33 的next是空2. 做链表题最容易犯的毛病先提前说一下不然你后面老踩坑。2.1 只盯着值不盯着指针数组题经常只关心数值。但链表题里最重要的往往不是值而是这个节点现在指向谁。2.2 改指针前不先保存下一个节点比如你要改cur-next prev;那你必须先想清楚cur 原来后面的链会不会丢很多人一上来就改结果后面全断了。2.3 不画图链表题前期真的建议你边看边画1 - 2 - 3 - 4把每个指针移动过程画出来会清楚很多。3. 第一题反转链表3.1 题目大意给你单链表的头节点head请你反转链表并返回反转后的链表。比如1 - 2 - 3 - 4 - 5反转后变成5 - 4 - 3 - 2 - 13.2 这题第一眼该想到什么这题是链表题的入门必修课。它本质上就是把每个节点的 next 方向反过来。原来是1 - 2改完要变成2 - 1所以这题的核心不是值变了而是指针方向变了3.3 这题最经典的三个指针这题建议你直接背这三个变量prev前一个节点cur当前节点nxt先保存当前节点后面的节点为什么一定要有nxt因为你马上要改cur-next prev;如果你不提前把后面存起来链就断了。3.4 代码class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* nxt cur-next; cur-next prev; prev cur; cur nxt; } return prev; } };3.5 代码怎么理解假设原链表是1 - 2 - 3 - nullptr一开始prev nullptrcur 1第一步先存下一个节点nxt cur-next也就是nxt 2然后改方向cur-next prev也就是1 - nullptr然后往前推进prev 1cur 2第二步同理先记住3把2-next指向1再推进最后就会变成3 - 2 - 1 - nullptr3.6 这题你要记住的核心链表反转固定模板ListNode* prev nullptr; ListNode* cur head; while (cur) { ListNode* nxt cur-next; cur-next prev; prev cur; cur nxt; } return prev;这个模板你后面会反复用到。3.7 这题最容易犯的错错误 1忘记先存nxt这会导致后面的链表丢失。错误 2最后返回head反转后新的头节点不是原来的head而是最后的prev。4. 第二题合并两个有序链表4.1 题目大意将两个升序链表合并为一个新的升序链表并返回。比如l1 1 - 2 - 4 l2 1 - 3 - 4合并后1 - 1 - 2 - 3 - 4 - 44.2 这题第一眼该想到什么这题本质上和数组里的“归并”很像两边都已经有序每次取较小的那个接到答案后面所以核心就是用一个尾指针不断接新节点4.3 为什么经常要用虚拟头节点 dummy链表题里dummy特别常见。比如ListNode* dummy new ListNode(0); ListNode* cur dummy;你可以把dummy理解成先弄一个假头方便统一处理。这样就不用纠结第一个节点该怎么接头节点会不会变空链表怎么办最后返回dummy-next就行。4.4 代码class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* dummy new ListNode(0); ListNode* cur dummy; while (list1 ! nullptr list2 ! nullptr) { if (list1-val list2-val) { cur-next list1; list1 list1-next; } else { cur-next list2; list2 list2-next; } cur cur-next; } if (list1 ! nullptr) cur-next list1; if (list2 ! nullptr) cur-next list2; return dummy-next; } };4.5 代码怎么理解这里的cur始终表示当前合并链表的最后一个节点。每次比较list1-vallist2-val谁小就把谁接到cur-next后面。然后被接走的那个链表往后走一步cur也往后走一步直到有一个链表空了剩下的直接整段接上。4.6 这题你要记住的核心合并有序链表固定思路开一个dummy用cur指向当前尾部每次接较小的节点最后把剩余部分直接接上4.7 这题最容易犯的错错误 1不使用 dummy导致头节点处理很乱前期强烈建议用。错误 2循环结束后忘记接剩余部分比如某一边还没走完要整段接上。5. 第三题删除链表的倒数第 N 个结点5.1 题目大意给你一个链表删除链表的倒数第n个结点并且返回链表的头节点。比如1 - 2 - 3 - 4 - 5, n 2删除后1 - 2 - 3 - 55.2 这题第一眼该想到什么倒数第n个很容易想到一个思路先遍历一次求长度再遍历一次找到正数第几个然后删除这个能做。但 Hot100 更经典的写法是快慢指针5.3 为什么快慢指针能做核心思路是让fast先走n步。然后slow和fast一起走。这样当fast到末尾的时候slow就会刚好走到“待删除节点的前一个位置”。这个思路非常经典。5.4 为什么还要 dummy因为有一种特殊情况删除的是头节点比如1 - 2 n 2这时候删的是第一个节点。如果没有dummy处理起来会麻烦很多。所以标准写法一般是dummy-next head从dummy开始做快慢指针5.5 代码class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); ListNode* fast dummy; ListNode* slow dummy; for (int i 0; i n; i) { fast fast-next; } while (fast-next ! nullptr) { fast fast-next; slow slow-next; } slow-next slow-next-next; return dummy-next; } };5.6 这段代码怎么理解先让fast走n步。这时fast比slow多走了n个节点接着两个一起走。当fast-next nullptr时说明fast已经在最后一个节点slow正好在待删除节点前一个位置然后直接slow-next slow-next-next;就把目标节点删掉了。5.7 这题你要记住的核心链表倒数问题很常用快慢指针本质是制造一个固定间距。这个间距一旦建立起来后面同时移动就行。5.8 这题最容易犯的错错误 1快指针起点不对前期建议fast和slow都从dummy出发。错误 2循环条件写错常见写法是while (fast-next ! nullptr)这样最后slow才会停在待删节点前一个位置。6. 第四题环形链表6.1 题目大意给你一个链表判断链表中是否有环。也就是说链表最后某个节点的next不是空而是指回前面某个节点。有环就返回true无环返回false。6.2 这题第一眼该想到什么一看到“是否有环”最经典的方法就是快慢指针也叫龟兔赛跑6.3 为什么快慢指针能判断有环如果链表没有环快指针会先走到空不可能和慢指针相遇如果链表有环快指针一次走两步慢指针一次走一步快指针早晚会在环里追上慢指针这个思路很经典。6.4 代码class Solution { public: bool hasCycle(ListNode *head) { ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { return true; } } return false; } };6.5 这题最重要的判断条件循环条件一定要注意while (fast ! nullptr fast-next ! nullptr)因为fast要一次走两步所以你必须先确保fast不是空fast-next也不是空不然会访问非法位置。6.6 这题要记住的核心判环固定模板slow一次一步fast一次两步相遇说明有环快指针能走到空说明无环7. 第五题环形链表 II7.1 题目大意这题比上一题更进一步。不是只问你有没有环而是问你环的入口节点在哪里如果没有环返回nullptr。7.2 这题第一眼该想到什么先别慌。这题依然是快慢指针只不过比上一题多一步第一步先判断有没有环第二步如果有环找入口7.3 找入口这个结论先直接记住这是链表里一个非常经典的结论当快慢指针第一次相遇后让一个指针回到头节点另一个指针留在相遇点。然后两个指针每次都走一步。它们再次相遇的地方就是环的入口。你现在先把它当结论用后面熟了再深究推导。7.4 代码class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { ListNode* p1 head; ListNode* p2 slow; while (p1 ! p2) { p1 p1-next; p2 p2-next; } return p1; } } return nullptr; } };7.5 代码怎么理解先用和上一题一样的方法找相遇点。如果根本没相遇那就说明没有环返回nullptr。如果相遇了p1从头节点开始p2从相遇点开始两个都一次走一步最后相遇的位置就是入口。7.6 这题你现阶段怎么学最合适前期你不用强迫自己把数学推导全啃下来。先做到会写会用知道这是快慢指针的经典结论就够了。后面做多了再回头看会更容易懂。8. 这五道题放在一起你要看出什么这五题表面不一样但背后其实就是链表最核心的几个套路。8.1 反转链表核心改 next 指向三指针配合8.2 合并两个有序链表核心dummy 虚拟头节点尾插法思维两链表归并8.3 删除链表的倒数第 N 个结点核心dummy快慢指针制造间距8.4 环形链表核心快慢指针判环8.5 环形链表 II核心快慢指针先相遇再找入口9. 链表题模板9.1 反转链表模板ListNode* prev nullptr; ListNode* cur head; while (cur) { ListNode* nxt cur-next; cur-next prev; prev cur; cur nxt; } return prev;9.2 dummy 模板ListNode* dummy new ListNode(0); ListNode* cur dummy;最后一般返回dummy-next9.3 快慢指针模板ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; }这个模板在链表题里非常高频。10. 本篇总结这一篇正式进入了Hot100 链表专题。现在最重要的不是追求链表题全会而是先把最核心的几个套路练熟反转链表三指针合并链表dummy 尾插删除倒数第 N 个快慢指针判环快慢指针找环入口快慢指针经典结论把这 5 个吃下来后面很多链表题都会顺很多。11. 给自己记的几句话可以直接记链表题先想清楚 next 要指向谁改指针前先保存后面节点链表头节点容易变所以常用 dummy链表倒数问题常用快慢指针链表判环和找入口都是快慢指针经典题