C++刷 LeetCode Hot100 笔记（八）链表专题（下）：相交链表、回文链表、两数相加、两两交换链表中的节点、随机链表的复制

前一篇我们已经把链表最核心的 5 道基础题过了一遍反转链表合并两个有序链表删除链表的倒数第 N 个结点环形链表环形链表 II这一篇继续只按Hot100 链表题往下讲再吃掉 5 道高频题相交链表回文链表两数相加两两交换链表中的节点随机链表的复制这几道题一过你对链表的感觉会明显好很多。因为这几题刚好覆盖了链表里几个特别常见的方向双指针对齐找中点 反转模拟进位成组改指针哈希表记录节点映射1. 这一篇先学会什么这一篇你重点不是背答案而是要学会几个链表套路1.1 相交链表学会一种非常妙的双指针长度对齐思路1.2 回文链表学会找中点 反转后半段 比较1.3 两数相加学会模拟竖式加法 进位处理1.4 两两交换链表中的节点学会dummy 局部改指针1.5 随机链表的复制学会哈希表建立“旧节点 - 新节点”的映射2. 第一题相交链表2.1 题目大意给你两个单链表的头节点headA和headB找出它们相交的起始节点。如果两个链表没有相交返回nullptr。注意这里说的“相交”不是值一样而是真的是同一个节点也就是说后面那一段链表是共用的。比如A: 4 - 1 \ 8 - 4 - 5 B: 5 - 6 - 1 /这里相交点就是值为8的那个节点。2.2 这题第一眼该想到什么这题很容易先想到一个笨办法先算 A 长度再算 B 长度让长的那个先走几步然后一起走看什么时候相遇这个能做而且思路是对的。但 Hot100 里更经典、也更巧的写法是双指针换头走2.3 为什么双指针换头走这么妙设链表 A 长度是a c链表 B 长度是b c后面的c是相交部分我们让两个指针pA从 A 开始走pB从 B 开始走当某个指针走到空了就去另一条链表头重新开始走。也就是pA走完 A再走 BpB走完 B再走 A这样它们走过的总长度就一样了a c b b c a总长度相同所以如果有交点就一定会在交点相遇。如果没有交点最后会一起走到nullptr。这个思路真的很漂亮。2.4 代码class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode* pA headA; ListNode* pB headB; while (pA ! pB) { pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; } return pA; } };2.5 代码怎么理解循环条件是while (pA ! pB)只要两个指针还没相遇就继续走。每次走法是如果当前不是空就正常往后走如果已经走到空了就跳去另一条链表开头最后有两种结果情况 1有交点它们会在交点相遇。情况 2没交点它们会一起变成nullptr然后退出循环。2.6 这题要记住的核心相交链表固定技巧双指针换头走自动对齐长度。这是链表题里特别经典的技巧。2.7 这题最容易犯的错错误 1把“值相等”当成“节点相同”这题比较的是指针是不是同一个节点不是val是否一样。比较应该是pA pB不是pA-val pB-val3. 第二题回文链表3.1 题目大意给你一个单链表的头节点head判断这个链表是不是回文链表。比如1 - 2 - 2 - 1是回文。1 - 2不是回文。3.2 这题第一眼该想到什么最容易想到的方法是先把链表值取出来放进数组然后双指针判断数组是不是回文这个做法能做出来也不算错。但链表专题里更经典的方法是找中点 反转后半段 比较前后两段3.3 整体思路这题可以拆成三步第一步找链表中点用快慢指针。第二步反转后半段链表这样后半段顺序就倒过来了。第三步从头和后半段头一起比较如果全都相等就是回文。3.4 为什么这样能做比如链表1 - 2 - 2 - 1找到中点后后半段是2 - 1反转后变成1 - 2前半段本来就是1 - 2这样就能一一比较了。3.5 代码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; } bool isPalindrome(ListNode* head) { if (head nullptr || head-next nullptr) return true; ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } ListNode* second reverseList(slow); ListNode* first head; while (second ! nullptr) { if (first-val ! second-val) { return false; } first first-next; second second-next; } return true; } };3.6 代码怎么理解第一步找中点while (fast ! nullptr fast-next ! nullptr)slow一次一步fast一次两步循环结束后slow会到中间附近。第二步反转后半段ListNode* second reverseList(slow);把从slow开始的后半部分反转。第三步比较first从头开始second从反转后的后半段开始只要first-val ! second-val就不是回文。如果都相等就是回文。3.7 这题要记住的核心回文链表经典套路快慢指针找中点反转后半段两段比较这题其实是把找中点反转链表两个基础技巧合在一起用了。3.8 这题最容易犯的错错误 1中点找完后不知道从哪开始反转前期你先记住这一版写法直接从slow开始反转。错误 2比较时循环条件写错因为后半段长度更短或者相等所以通常用while (second ! nullptr)4. 第三题两数相加4.1 题目大意给你两个非空链表表示两个非负整数。它们每位数字是按照逆序存储的并且每个节点只能存一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。比如l1 2 - 4 - 3 l2 5 - 6 - 4表示的其实是342 465 807所以返回7 - 0 - 84.2 这题第一眼该想到什么这题本质上就是模拟竖式加法你不用把链表转成整数再加因为那样会有溢出问题而且也没必要。直接一位一位加就行。4.3 这题的关键点每一轮要处理三部分当前l1这一位当前l2这一位上一位传下来的进位carry总和sum x y carry然后当前位是sum % 10新进位是sum / 10这和小学竖式加法一模一样。4.4 代码class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dummy new ListNode(0); ListNode* cur dummy; int carry 0; while (l1 ! nullptr || l2 ! nullptr || carry ! 0) { int x (l1 ! nullptr) ? l1-val : 0; int y (l2 ! nullptr) ? l2-val : 0; int sum x y carry; carry sum / 10; cur-next new ListNode(sum % 10); cur cur-next; if (l1 ! nullptr) l1 l1-next; if (l2 ! nullptr) l2 l2-next; } return dummy-next; } };4.5 代码怎么理解这里的dummy还是虚拟头节点。cur表示结果链表当前的尾巴。每轮做这些事第一步取当前两位数字如果某一条链表已经走完了那一位就按 0 算。int x (l1 ! nullptr) ? l1-val : 0; int y (l2 ! nullptr) ? l2-val : 0;第二步算总和int sum x y carry;第三步更新进位carry sum / 10;第四步当前位加入结果链表cur-next new ListNode(sum % 10);4.6 这题要记住的两数相加固定模型dummycur 尾插carry 维护进位谁空了就补 04.7 这题最容易犯的错错误 1忘了最后还有进位比如5 5 10最后还要多加一个节点1。所以循环条件不能只写while (l1 || l2)要写成while (l1 || l2 || carry)5. 第四题两两交换链表中的节点5.1 题目大意给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你不能只是单纯地改变节点内部的值而是要真正交换节点。比如1 - 2 - 3 - 4交换后变成2 - 1 - 4 - 35.2 这题第一眼该想到什么这题看起来麻烦其实本质上还是局部改指针每次只处理两个节点一组。比如当前这组是a - b交换后要变成b - a但别忘了它前后还连着别的节点所以你要考虑的不只是这两个点还有这一组前面的节点这一组后面的节点这也是为什么这题很适合用dummy 虚拟头节点5.3 先把一组节点的关系想清楚假设当前有pre - a - b - nextPair交换以后要变成pre - b - a - nextPair要改的指针有三个pre-next b a-next nextPair b-next a这就是这题的核心。5.4 代码class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* dummy new ListNode(0, head); ListNode* pre dummy; while (pre-next ! nullptr pre-next-next ! nullptr) { ListNode* a pre-next; ListNode* b a-next; ListNode* nextPair b-next; pre-next b; b-next a; a-next nextPair; pre a; } return dummy-next; } };5.5 代码怎么理解这里的pre表示当前这一组前面的那个节点。进入循环时必须保证当前至少还有两个节点可交换while (pre-next ! nullptr pre-next-next ! nullptr)然后设a pre-nextb a-next交换后pre-next bb-next aa-next nextPair最后pre a;因为交换完后a成了这一组的后一个节点它正好是下一组的前驱。5.6 这题你要记住的核心成组交换链表节点dummy 很重要先把一组里的几个角色命名清楚再按顺序改指针这类题最怕乱所以一定要先把图想清楚。5.7 这题最容易犯的错错误 1直接上手改没先保存nextPair一旦没保存后面的链就容易断。错误 2交换完以后pre不知道怎么走记住pre a;因为交换后a落在后面。6. 第五题随机链表的复制6.1 题目大意给你一个链表每个节点除了有next指针还有一个random指针可能指向链表中的任意节点也可能指向空。要求你复制这个链表并返回复制后的头节点。注意不能只复制值必须复制节点关系也就是说新链表每个节点都要是新建出来的节点但它们的next和random关系要和原链表对应上。6.2 这题第一眼该想到什么这题最麻烦的地方在于next还好办random可能随便指向前面、后面、自己、或者空所以如果你只一边遍历一边建很可能在设置random的时候对应的新节点还没建出来。这时候最自然的方法就是哈希表建立映射也就是旧节点 - 新节点6.3 这题为什么适合哈希表假设原链表里某个节点是oldNode它对应的新节点是newNode。那我们就用哈希表存mp[oldNode] newNode这样以后不管遇到oldNode-nextoldNode-random我们都能很快找到对应的新节点。6.4 代码class Solution { public: Node* copyRandomList(Node* head) { if (head nullptr) return nullptr; unordered_mapNode*, Node* mp; Node* cur head; while (cur ! nullptr) { mp[cur] new Node(cur-val); cur cur-next; } cur head; while (cur ! nullptr) { mp[cur]-next (cur-next ! nullptr) ? mp[cur-next] : nullptr; mp[cur]-random (cur-random ! nullptr) ? mp[cur-random] : nullptr; cur cur-next; } return mp[head]; } };6.5 代码怎么理解这题分两遍遍历。第一遍只负责创建新节点mp[cur] new Node(cur-val);这一遍先把所有“旧节点对应的新节点”建好。第二遍补 next 和 random 关系mp[cur]-next ... mp[cur]-random ...因为现在所有新节点都已经存在了所以可以放心连边。6.6 这题你要记住的核心随机链表复制固定思路哈希表存映射旧节点 - 新节点第一遍建点第二遍连边这道题本质上不是普通链表题了它更像图的拷贝思想因为一个节点可以通过random指向任意别的节点。6.7 这题最容易犯的错错误 1只复制 val没有复制指针关系那不叫真正复制。错误 2第一遍还没建完所有节点就急着连 random容易找不到对应节点所以最好分成两遍。7. 这五道题放在一起你要看出什么这一篇最重要的不是你又做了 5 道题而是你要看出来链表题其实就是在练几种高频套路7.1 相交链表核心双指针换头自动对齐长度7.2 回文链表核心快慢指针找中点反转后半段两段比较7.3 两数相加核心模拟加法carry 进位dummy 尾插7.4 两两交换链表中的节点核心dummy一组一组改指针7.5 随机链表的复制核心哈希表记录节点映射先建点再连边8. 几个模板8.1 相交链表模板ListNode* pA headA; ListNode* pB headB; while (pA ! pB) { pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; } return pA;8.2 回文链表模板思路1. 快慢指针找中点 2. 反转后半段 3. 前后比较8.3 两数相加模板ListNode* dummy new ListNode(0); ListNode* cur dummy; int carry 0; while (l1 || l2 || carry) { int x l1 ? l1-val : 0; int y l2 ? l2-val : 0; int sum x y carry; carry sum / 10; cur-next new ListNode(sum % 10); cur cur-next; if (l1) l1 l1-next; if (l2) l2 l2-next; }8.4 两两交换模板核心关系pre - a - b - nextPair 变成 pre - b - a - nextPair8.5 随机链表复制模板unordered_mapNode*, Node* mp; // 第一遍建点 // 第二遍连 next 和 random9. 链表专题总结会这些基础动作反转链表用 dummy 处理头节点用快慢指针找中点 / 判环 / 制造间距局部交换节点用哈希表存节点映射会这些经典 Hot100 链表题反转链表合并两个有序链表删除链表的倒数第 N 个结点环形链表环形链表 II相交链表回文链表两数相加两两交换链表中的节点随机链表的复制到这一步你的链表基础其实已经很不错了。