尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
【算法从零到千】【59-65】链表专题
1. 两数相加2. 两数相加https://leetcode.cn/problems/add-two-numbers/https://leetcode.cn/problems/add-two-numbers/给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头写法迭代class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int carry0,all0; ListNode* pheadnew ListNode(0);ListNode* curphead; while(l1l2) { alll1-vall2-valcarry; if(all10){carry1;all%10;} else{carry0;} cur-nextnew ListNode(all); curcur-next; l1l1-next;l2l2-next;all0; } while(l1||l2) { if(l1){alll1-valcarry; l1l1-next;} if(l2){alll2-valcarry; l2l2-next;} if(all10){carry1;all%10;} else{carry0;} cur-nextnew ListNode(all);all0; curcur-next; } if(carry1) { cur-nextnew ListNode(1); curcur-next; } curphead-next; delete phead; return cur; } };优化写法class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { // 构造哑巴节点 dummy最后返回 dummy.next, 以方便处理新链表的头节点。 ListNode* dummy new ListNode(0); ListNode* node dummy; // node 一直会变化前进 int carrier 0; // 进位 // 只要有没走到头的链表或者进位不为 0 就一直前进。 while (l1 || l2 || carrier) { // 求和考虑可能有链表走到头 int sum (l1 ? l1-gt;val : 0) (l2 ? l2-gt;val : 0) carrier; // 在尾部添加节点 node-gt;next new ListNode(sum % 10); node node-gt;next; // 更新进位并向两个链表尾部前进 carrier sum / 10; if (l1) l1 l1-gt;next; if (l2) l2 l2-gt;next; } ListNode* result dummy-gt;next; // 保存结果链表的头节点 delete dummy; // 释放哑节点的内存 return result; } };2. 删除链表的倒数第N个节点19. 删除链表的倒数第 N 个结点https://leetcode.cn/problems/remove-nth-node-from-end-of-list/https://leetcode.cn/problems/remove-nth-node-from-end-of-list/给你一个链表删除链表的倒数第n个结点并且返回链表的头结点写法一双指针class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* curhead;ListNode* prevnullptr; int size0; while(cur) {size;curcur-next;} curhead;int aimsize-n; while(aim--) { prevcur; curcur-next; } if(curhead) return head-next; if(head-next) prev-nextcur-next; else return nullptr; return head; } };写法二快慢指针class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { // 由于可能会删除链表头部用哨兵节点简化代码 ListNode dummy{0, head}; ListNode* left dummy; ListNode* right dummy; while (n--) { right right-next; // 右指针先向右走 n 步 } while (right-next) { left left-next; right right-next; // 左右指针一起走 } // 左指针的下一个节点就是倒数第 n 个节点 ListNode* nxt left-next; left-next left-next-next; delete nxt; return dummy.next; } };3. 排序链表148. 排序链表https://leetcode.cn/problems/sort-list/https://leetcode.cn/problems/sort-list/给你链表的头结点head请将其按 升序 排列并返回 排序后的链表写法一STLclass Solution { public: ListNode* sortList(ListNode* head) { multimapint,ListNode* hash; ListNode* curhead; while(cur) { hash.insert({cur-val,cur}); curcur-next; } ListNode* pheadnew ListNode(0);curphead; for(auto e:hash) { cur-nexte.second; curcur-next; } cur-nextnullptr; return phead-next; } };写法二归并排序class Solution { public: ListNode* sortList(ListNode* head) { return mergeSort(head); } /** * 对给定的链表进行归并排序 */ ListNode* mergeSort(ListNode* head){ // 如果链表为空或只有一个节点无需排序直接返回 if(!head || !head-gt;next){ return head; } // 获取链表的中间节点分别对左右子链表进行排序 ListNode* mid getMid(head); ListNode* rightSorted mergeSort(mid-gt;next); // 排序右子链表 if(mid)mid-gt;next nullptr; // 断开两段子链表 ListNode* leftSorted mergeSort(head); // 排序左子链表 return mergeTwoLists(leftSorted, rightSorted); // 两个子链表必然有序合并两个有序的链表 } /** * 获取以head为头节点的链表中间节点 * 如果链表长度为奇数返回最中间的那个节点 * 如果链表长度为偶数返回中间靠左的那个节点 */ ListNode* getMid(ListNode* head){ if(!head)return head; ListNode* slow head, *fast head-gt;next; // 快慢指针慢指针初始为 while(fast ! nullptr amp;amp; fast-gt;next ! nullptr) { fast fast-gt;next-gt;next; // 快指针每次移动两个节点 slow slow-gt;next; // 慢指针每次移动一个节点 } return slow; // 快指针到达链表尾部时慢指针即指向中间节点 } /** * 合并两个有序链表list1和list2 */ ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* dummy new ListNode(); // 伪头节点用于定位合并链表的头节点 ListNode* node dummy; // 新链表当前的最后一个节点初始为伪头节点 // 直到两个链表都遍历完了合并结束 while(list1 ! nullptr || list2 ! nullptr){ int val1 list1 nullptr ? 50001 : list1 -gt; val; // 如果链表1已经遍历完val1取最大值保证链表2的节点被选择到 int val2 list2 nullptr ? 50001 : list2 -gt; val; // 如果链表2已经遍历完val2取最大值保证链表1的节点被选择到 if(val1 lt; val2){ // 链表1的节点值更小加入到合并链表并更新链表1指向的节点 node -gt; next list1; list1 list1 -gt; next; }else{ // 链表2的节点值更小加入到合并链表并更新链表2指向的节点 node -gt; next list2; list2 list2 -gt; next; } node node -gt; next; // 更新合并链表当前的最后一个节点指向 } return dummy -gt; next; // 伪头节点的下一个节点即为合并链表的头节点 } };4. 重排链表4LCR 026. 重排链表https://leetcode.cn/problems/LGjMqU/https://leetcode.cn/problems/LGjMqU/给定一个单链表L的头节点head单链表L表示为L0 → L1 → … → Ln-1 → Ln请将其重新排列后变为L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …不能只是单纯的改变节点内部的值而是需要实际的进行节点交换写法一STL映射class Solution { public: void reorderList(ListNode* head) { if (!head-next) return; //处理边界 maplt;int,ListNode*gt; index;//记录位置 ListNode* curhead;int i0; while(cur) { index[i]cur; curcur-gt;next; } i--;//保证索引正确 curhead;int j1;//前后挨个插入 while(jlt;i) { cur-gt;nextindex[i--]; curcur-gt;next; if(i!j)//当ij只执行一次 {cur-gt;nextindex[j]; curcur-gt;next;} } cur-gt;nextnullptr; } };写法二反转三指针class Solution { public: void reorderList(ListNode* head) { ListNode* dummmy new ListNode(0); dummmy-next head; ListNode* slow dummmy; ListNode* fast dummmy; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } delete dummmy; dummmy nullptr; ListNode* headB slow-next; slow-next nullptr; ListNode* p2 reverseList(headB); ListNode* p1 head; ListNode* p3 nullptr; while (p2 ! nullptr) { p3 p1-next; p1-next p2; p1 p2; p2 p3; } } ListNode* reverseList(ListNode* head) { if (head nullptr) { return head; } ListNode* left nullptr; ListNode* cur head; ListNode* right nullptr; while (cur ! nullptr) { right cur-gt;next; cur-gt;next left; left cur; cur right; } return left; } };5. 两两交换链表中的节点24. 两两交换链表中的节点https://leetcode.cn/problems/swap-nodes-in-pairs/https://leetcode.cn/problems/swap-nodes-in-pairs/给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。写法一迭代class Solution { public: ListNode* swapPairs(ListNode* head) { if(!head||!head-next) return head; ListNode* curhead-next;ListNode* prevhead; //完成前两个 prev-nextcur-next; cur-nexthead;headcur; //后面再规律处理 curprev; prevhead;ListNode* prevvnullptr; while(cur-nextcur-next-next) { //规律移动 if(cur-nextcur-next-next){ prevvcur; curcur-next-next; prevprev-next-next; } //交换流程 prev-nextcur-next; cur-nextprev; prevv-nextcur; //保持cur与prev的前后关系 curprev; prevprevv-next; } //如果还剩下则为一个不用交换 return head; } };写法二递归class Solution { public: ListNode* swapPairs(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } ListNode* node1 head; ListNode* node2 head-gt;next; ListNode* node3 node2-gt;next; node1-gt;next swapPairs(node3); // 1 指向递归返回的链表头 node2-gt;next node1; // 2 指向 1 return node2; // 返回交换后的链表头节点 } };6. 合并K个升序链表23. 合并 K 个升序链表https://leetcode.cn/problems/merge-k-sorted-lists/https://leetcode.cn/problems/merge-k-sorted-lists/给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。写法一STL映射class Solution { public: ListNode* mergeKLists(vectorListNode* lists) { if(lists.size()0)return nullptr; if(lists.size()1)return lists[0]; //用哈希记录索引和节点地址 multimapint,ListNode* nodemap; for(auto e:lists) { ListNode* cure; while(cur) { nodemap.insert({cur-val,cur}); curcur-next; } } //重组链表 ListNode* pheadnew ListNode(0);ListNode* curphead; for(auto e:nodemap) { cur-nexte.second; curcur-next; } cur-nextnullptr; return phead-next; } };写法二优先级队列⭐⭐class Solution { public: ListNode* mergeKLists(vectorListNode* lists) { auto cmp [](const ListNode* a, const ListNode* b) { return a-val b-val; // 最小堆 }; priority_queueListNode*, vectorListNode*, decltype(cmp) pq; for (auto head : lists) { if (head) { pq.push(head); // 把所有非空链表的头节点入堆 } } ListNode dummy{}; // 哨兵节点作为合并后链表头节点的前一个节点 auto cur amp;dummy; while (!pq.empty()) { // 循环直到堆为空 auto node pq.top(); // 剩余节点中的最小节点 pq.pop(); if (node-gt;next) { // 下一个节点不为空 pq.push(node-gt;next); // 下一个节点有可能是最小节点入堆 } cur-gt;next node; // 把 node 添加到新链表的末尾 cur cur-gt;next; // 准备合并下一个节点 } return dummy.next; // 哨兵节点的下一个节点就是新链表的头节点 } };非常重要7. K个一组翻转链表25. K 个一组翻转链表https://leetcode.cn/problems/reverse-nodes-in-k-group/https://leetcode.cn/problems/reverse-nodes-in-k-group/给你链表的头节点head每k个节点一组进行翻转请你返回修改后的链表。k是一个正整数它的值小于或等于链表的长度。如果节点总数不是k的整数倍那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。写法一栈class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { if (k 1) return head; stackListNode* st; ListNode* pheadnew ListNode(0);ListNode* pcurphead; ListNode* curhead; //统计节点数量 int size0; while(cur){curcur-next;size;} //按k的数量依次处理 int n0,count0;curhead; while(countksize) { while(nkcur) { st.push(cur); curcur-next; n;count; } while(!st.empty()) { pcur-nextst.top(); st.pop(); pcurpcur-next; } n0; } //处理末尾情况 if(countsize) pcur-nextcur; else pcur-nextnullptr; curphead-gt;next; delete phead; return cur; } };写法二递归class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { ListNode *p head; for(int i 0; i k; i) { if(!p) return head; p p-next; } ListNode *q head; ListNode *pre nullptr; while(q ! p) { ListNode *tmp q-gt;next; q-gt;next pre; pre q; q tmp; } head-gt;next reverseKGroup(p, k); return pre; } };
RELATED

相关推荐

SAP UI5 里有没有 RxJS switchMap 的对应能力,以及怎样真正实现 Latest Wins

SAP UI5 里有没有 RxJS switchMap 的对应能力,以及怎样真正实现 Latest Wins

直接给出判断,SAP UI5 自身没有一个名称叫 switchMap、并且能够与 RxJS switchMap 一一对应的原生 Operator。SAP UI5 的事件系统、Binding 系统、Promise 异步调用以及 OData Model 都能覆盖 switchMap 的部分使用场景,但它们并没有组成 RxJS 那种完整的 Observable 管道体系…

📅 2026/11/5 13:47:20
RevokeMsgPatcher:微信QQ防撤回补丁怎么用?

RevokeMsgPatcher:微信QQ防撤回补丁怎么用?

RevokeMsgPatcher:微信QQ防撤回补丁怎么用? 【免费下载链接】RevokeMsgPatcher :trollface: A hex editor for WeChat/QQ/TIM - PC版微信/QQ/TIM防撤回补丁(我已经看到了,撤回也没用了) 项目地址: https://gitcode.c…

📅 2026/11/5 17:48:57
3 步免费把 NCM 加密音乐转成 MP3:ncmdump 离线转换入门教程

3 步免费把 NCM 加密音乐转成 MP3:ncmdump 离线转换入门教程

3 步免费把 NCM 加密音乐转成 MP3:ncmdump 离线转换入门教程 【免费下载链接】ncmdump 项目地址: https://gitcode.com/gh_mirrors/ncmd/ncmdump ncmdump 是一款完全免费、开源的本地加密音乐转换工具,把网易云 NCM 加密文件转成通用 MP3。全程无…

📅 2026/11/15 13:58:28
MORE NEWS

更多资讯

📰

河北建筑电工证多少钱?工地太忙根本没时间复习考试?郑州报考避坑指南来了

河北建筑电工证多少钱?工地太忙根本没时间复习考试?郑州报考避坑指南来了 工地太忙根本没时间复习考试,这不是个例,而是大多数建筑工人的真实写照。特别是像河北建筑电工证这种必须通过考试才能上岗的证书,很多工人一听说要考试就犯愁,怕耽误工期,怕学…

📰

电工证高压证考试试题怎么准备?上岗必备的实操备考攻略来了

电工证高压证考试试题怎么准备?上岗必备的实操备考攻略来了 实操考试心里没底怕挂科,这是很多准备考电工证高压证的朋友最真实的感受。尤其是刚接触这个行业的朋友,面对考试题型和内容,常常感到无从下手。如果你在信阳浉河区,正在准备电工证高压证考试试…

📰

牡丹江电工证申办条件网上查询怎么搞?证书过期了不知道怎么复审延期

牡丹江电工证申办条件网上查询怎么搞?证书过期了不知道怎么复审延期 证书过期了不知道怎么复审延期,你是不是也遇到过这种情况?网上查了又查,结果还是没个准信,浪费时间不说,还影响工作。今天就来聊聊牡丹江电工证申办条件和网上查询那些事,让你少走弯…

📰

阜阳市电工证报名保姆级教程:外省证书怎么转?薪资前景全解析

阜阳市电工证报名保姆级教程:外省证书怎么转?薪资前景全解析 之前考的证在外省能不能转过来?这几乎是每个在外地打拼的电工朋友心头最大的疑问。尤其是像你这样在济源从事公路工程的朋友,可能手里握着外地考的电工证,但又想在阜阳继续发展,或者计划转行…

📰

芜湖怎么查电工证和官方报名入口全攻略,转岗电工别再走弯路

芜湖怎么查电工证和官方报名入口全攻略,转岗电工别再走弯路 现在找工作,没有电工证连面试都过不了,尤其在芜湖这样的制造业城市,电工证是基本门槛。很多人在问“ 芜湖怎么查电工证 ”,还有人不知道 官方报名入口…

📰

广西电工证多少钱?上岗必备的费用与职业前景全解析

广西电工证多少钱?上岗必备的费用与职业前景全解析 之前考的证在外省能不能转过来?这个问题让不少转岗或者换城市打工的电工朋友愁得不行。今天咱们就从“广西电工证多少钱”切入,聊聊电工证的费用、有效期、考试内容、证书变更流程,还有在广西做电工到底…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬