【算法从零到千】【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; } };