算法：链表：指针变化与环

1. 206.反转链表给你单链表的头节点 head请你反转链表并返回反转后的链表。反转完成后pre为反转前的尾节点反转后的头结点cur为反转前的尾节点的后一个节点。/** * Definition for singly-linked list. * 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) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { // 循环里面四行代码先得nxt再翻转再更改pre和cur ListNode* pre nullptr; ListNode* cur head; while(cur){ ListNode* nxt cur - next; cur - next pre; pre cur; cur nxt; } return pre; } };2. 25.K个一组翻转链表给你链表的头节点head每k个节点一组进行翻转请你返回修改后的链表。k是一个正整数它的值小于或等于链表的长度。如果节点总数不是k的整数倍那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。思路关键在于理清各个指针的变化将preTail, curTail, pre, cur连在一起。pre为反转前的尾节点反转后的头结点cur为反转前的尾节点的后一个节点即下一个待反转链表的头结点每次反转后当前链表的尾部总是 nullptr所以当前反转完成的链表头需要与上一个反转完成的链表尾连接当前反转完成的链表尾不一定需要与下一个未反转的链表头连接因为下一个链表反转后还是会断开但是如果下一个链表长度不够k就不会反转导致失去最后一段链表所以为了避免这个情况也需要与下一个链表头连接即每次反转完成后与前面的尾相连与后面的头相连。/** * Definition for singly-linked list. * 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) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { ListNode* cur head; int n 0; while(cur){ n; cur cur - next; } ListNode* dummy new ListNode(0, head); ListNode* preTail dummy; // 上一个已反转链表的尾 cur head; // 从头节点开始反转 // 最后k个不用反转 while(n k){ n n - k; ListNode* pre nullptr; ListNode* curTail cur; // 当前已反转链表的尾就是未反转前的头 for(int i 0; i k; i){ ListNode* nxt cur - next; cur - next pre; pre cur; cur nxt; } // 反转完成此时pre就是新链表的头cur就是下一个待反转链表的头 preTail - next pre; preTail curTail; curTail - next cur; } return dummy - next; } };3. 23.合并K个升序链表给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。思路链表的归并排序自底向上步长不断增加。/** * Definition for singly-linked list. * 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) {} * }; */ class Solution { public: ListNode* mergerTwoLists(ListNode* head1, ListNode* head2){ ListNode* dummy new ListNode(); ListNode* cur dummy; ListNode* cur1 head1; ListNode* cur2 head2; while(cur1 cur2){ if(cur1 - val cur2 - val){ cur - next cur2; cur2 cur2 - next; }else{ cur - next cur1; cur1 cur1 - next; } cur cur - next; } cur - next cur1 ? cur1 : cur2; return dummy - next; } ListNode* mergeKLists(vectorListNode* lists) { if(lists.empty()) return nullptr; int step 1; int n lists.size(); while(step n){ int idx 0; while(idx n){ ListNode* head1 lists[idx]; ListNode* head2 (idx step) n ? lists[idx step] : nullptr; lists[idx] mergerTwoLists(head1, head2); idx 2 * step; } step * 2; } return lists[0]; } };4. 148.排序链表给你链表的头结点head请将其按升序排列并返回排序后的链表。思路自底向上的归并排序与上一题相同外层循环确定步长内存循环进行合并。关键在于合并两个链表时要断开每个链表尾部合并后将当前链表头与上一个链表尾连接。/** * Definition for singly-linked list. * 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) {} * }; */ class Solution { public: // 自底向上的归并排序大循环判断步长[1, n)小循环cur合并链表关键在于两个链表的头尾节点断开与接上 ListNode* mergeTwoLists(ListNode* headA, ListNode* headB){ ListNode* curA headA, *curB headB; ListNode* dummy new ListNode(0); ListNode* cur dummy; while(curA curB){ if(curA - val curB - val){ cur - next curB; curB curB - next; }else{ cur - next curA; curA curA - next; } cur cur - next; } cur - next curA ? curA : curB; return dummy - next; } ListNode* sortList(ListNode* head) { int n 0; ListNode* cur head; while(cur){ n; cur cur - next; } int step 1; ListNode* dummy new ListNode(0, head); while(step n){ ListNode* preTail dummy; cur dummy - next; while(cur){ // 1. 第1段[head1, tail1] ListNode* head1 cur; for(int i 1; i step cur; i){ cur cur - next; } ListNode* tail1 cur; // 2. 获取第2段头并与第1段尾断开 ListNode* head2 nullptr; if(tail1){ head2 tail1 - next; tail1 - next nullptr; } // 3. 获取第2段尾 cur head2; for(int i 1; i step cur; i){ cur cur - next; } ListNode* tail2 cur; // 4. 获取下一段头并与第2段尾断开 if(tail2){ cur tail2 - next; tail2 - next nullptr; } // 5. 合并为[newHead, newTail] ListNode* newHead mergeTwoLists(head1, head2); ListNode* newCur newHead; while(newCur newCur - next){ newCur newCur - next; } ListNode* newTail newCur; // 6. 与上一段连接 preTail - next newHead; preTail newTail; } step * 2; } return dummy - next; } };5. 146.LRU缓存请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现LRUCache类LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中则返回关键字的值否则返回-1。void put(int key, int value)如果关键字key已经存在则变更其数据值value如果不存在则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity则应该逐出最久未使用的关键字。函数get和put必须以O(1)的平均时间复杂度运行。思路需要哨兵头、哨兵尾和一个key到节点的map注意删除节点和把节点放到链表头时的各个节点的前后指针变化。class LRUCache { public: struct Node{ int key; int val; Node* prev; Node* next; Node(int k, int v):key(k), val(v){} }; unordered_mapint, Node* key2Node; Node* dummyHead; Node* dummyTail; int size; LRUCache(int capacity) { dummyHead new Node(-1, 0); dummyTail new Node(-1, 0); dummyHead - next dummyTail; dummyTail - prev dummyHead; dummyHead - prev nullptr; dummyTail - next nullptr; size capacity; } int get(int key) { if(key2Node.count(key)){ // 将该结点提到头 Node* cur key2Node[key]; cur - prev - next cur - next; cur - next - prev cur - prev; dummyHead - next - prev cur; cur - next dummyHead - next; cur - prev dummyHead; dummyHead - next cur; return cur - val; } return -1; } void put(int key, int value){ if(key2Node.count(key)){ Node* cur key2Node[key]; cur - val value; cur - prev - next cur - next; cur - next - prev cur - prev; dummyHead - next - prev cur; cur - next dummyHead - next; cur - prev dummyHead; dummyHead - next cur; }else{ if(key2Node.size() size){ // 满了需要先删除一个 Node* cur dummyTail - prev; cur - prev - next dummyTail; dummyTail - prev cur - prev; key2Node.erase(cur - key); } Node* cur new Node(key, value); key2Node[key] cur; dummyHead - next - prev cur; cur - next dummyHead - next; cur - prev dummyHead; dummyHead - next cur; } } }; /** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj new LRUCache(capacity); * int param_1 obj-get(key); * obj-put(key,value); */6. 460.LFU缓存请你为 最不经常使用LFU缓存算法设计并实现数据结构。实现LFUCache类LFUCache(int capacity)- 用数据结构的容量capacity初始化对象int get(int key)- 如果键key存在于缓存中则获取键的值否则返回-1。void put(int key, int value)- 如果键key已存在则变更其值如果键不存在请插入键值对。当缓存达到其容量capacity时则应该在插入新项之前移除最不经常使用的项。在此问题中当存在平局即两个或更多个键具有相同使用频率时应该去除最久未使用的键。为了确定最不常使用的键可以为缓存中的每个键维护一个使用计数器。使用计数最小的键是最久未使用的键。当一个键首次插入到缓存中时它的使用计数器被设置为1(由于 put 操作)。对缓存中的键执行get或put操作使用计数器的值将会递增。函数get和put必须以O(1)的平均时间复杂度运行。思路每个频率对应一个LRU链表对其操作时把该节点的频率加1放到频率更高的LRU链表需要额外的对象频率到链表的map当前的最小频率创建新链表的函数。class LFUCache { public: struct Node { int key; int val; int freq; Node* prev; Node* next; Node(int k, int v) : key(k),val(v){} }; int minfreq; int size; unordered_mapint, Node* key2Node; unordered_mapint, pairNode*, Node* freq2lst; LFUCache(int capacity) { minfreq 0; size capacity; } pairNode*, Node* getLst(int freq){ if(!freq2lst.count(freq)){ Node* dummyHead new Node(-1, -1); Node* dummyTail new Node(-1, -1); dummyHead - next dummyTail; dummyHead - prev nullptr; dummyTail - next nullptr; dummyTail - prev dummyHead; freq2lst[freq] {dummyHead, dummyTail}; } return freq2lst[freq]; } int get(int key) { if(!key2Node.count(key)){ return -1; } Node* cur key2Node[key]; // 1. 获取原来所在的链表并删除该节点 auto [dummyHead, dummyTail] getLst(cur - freq); cur - prev - next cur - next; cur - next - prev cur - prev; // 2. 判断原链表是否为空 if(dummyHead - next - next nullptr){ // 判断是否需要更改minFreq if(minfreq cur - freq) minfreq; } // 3. 将该节点插入新链表 cur - freq; tie(dummyHead, dummyTail) getLst(cur - freq); dummyHead - next - prev cur; cur - next dummyHead - next; cur - prev dummyHead; dummyHead - next cur; return cur - val; } void put(int key, int value) { if(key2Node.count(key)){ // 节点已存在需要提出到新链表 // 1. 获取原来所在的链表并删除该节点 Node* cur key2Node[key]; auto [dummyHead, dummyTail] getLst(cur - freq); cur - prev - next cur - next; cur - next - prev cur - prev; // 2. 判断原链表是否为空 if(dummyHead - next - next nullptr){ // 判断是否需要更改minFreq if(minfreq cur - freq) minfreq; } // 3. 将该节点插入新链表 cur - freq; tie(dummyHead, dummyTail) getLst(cur - freq); dummyHead - next - prev cur; cur - next dummyHead - next; cur - prev dummyHead; dummyHead - next cur; cur - val value; return; } // 节点不存在 // 1.判断是否需要删除 if(key2Node.size() size){ // 满了需要删除一个 auto [dummyHead, dummyTail] getLst(minfreq); Node* cur dummyTail - prev; dummyTail - prev cur - prev; cur - prev - next dummyTail; key2Node.erase(cur - key); } minfreq 1; auto [dummyHead, dummyTail] getLst(minfreq); Node* cur new Node(key, value); cur - freq 1; key2Node[key] cur; dummyHead - next - prev cur; cur - next dummyHead - next; cur - prev dummyHead; dummyHead - next cur; } }; /** * Your LFUCache object will be instantiated and called as such: * LFUCache* obj new LFUCache(capacity); * int param_1 obj-get(key); * obj-put(key,value); */7. 环7.1 141.环形链表给你一个链表的头节点head判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。注意pos不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环则返回true。 否则返回false。思路快慢指针若存在环则双指针会相遇/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { ListNode* slow head; ListNode* fast head; while(fast fast - next){ slow slow - next; fast fast - next - next; if(slow fast) return 1; } return 0; } };7.2 142.环形链表Ⅱ给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。思路Floyd 判圈算法快慢指针相遇后一个指针从头走直到与慢指针相遇即为入环点。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* slow head; ListNode* fast head; while(fast fast - next){ slow slow - next; fast fast - next - next; if(fast slow){ ListNode* cur head; while(cur ! slow){ cur cur - next; slow slow - next; } return cur; } } return nullptr; } };7.3 287.寻找重复数给定一个包含n 1个整数的数组nums其数字都在[1, n]范围内包括1和n可知至少存在一个重复的整数。假设nums只有一个重复的整数返回这个重复的数。你设计的解决方案必须不修改数组nums且只用常量级O(1)的额外空间。思路将当前索引 i 上的值 nums[i] 看作当前节点的 next 指针索引/节点地址范围 [0, n]值/next指针范围 [1, n]于是必定有至少两个节点指向同一个节点即必定存在环遍历所有节点作为链表头由于每个链表都必定存在环如果以这个节点为头的链表不是自环则这次遍历必能找到入环点即重复数。class Solution { public: int findDuplicate(vectorint nums) { auto next [](int i) - int { return nums[i]; }; for(int i 0; i nums.size(); i){ // 循环遍历因为当前节点可能是自环 int slow i, fast i; while(slow ! next(slow)){ // 当前节点不是自环能找到重复数 slow next(slow); fast next(next(fast)); if(slow fast){ int cur i; while(cur ! slow){ cur next(cur); slow next(slow); } return cur; } } } return 0; // 不会执行到这里 } };或者去除外部头结点的遍历class Solution { public: int findDuplicate(vectorint nums) { auto next [](int i) - int { return nums[i]; }; // 循环遍历因为当前节点可能是自环 int slow 0, fast 0; while(1){ // 0 这个节点必定不可能自环故不用判断 slow next(slow); fast next(next(fast)); if(slow fast){ int cur 0; while(cur ! slow){ cur next(cur); slow next(slow); } return cur; } } return 0; // 不会执行到这里 } };因为0 不是 next 指针的范围所以当前索引为0的这个节点的next 不可能是自己不会是自环所以必定能找到入环点。7.4 457.环形数组是否存在循环存在一个不含0的环形数组nums每个nums[i]都表示位于下标i的角色应该向前或向后移动的下标个数如果nums[i]是正数向前下标递增方向移动nums[i]步如果nums[i]是负数向后下标递减方向移动abs(nums[i])步因为数组是环形的所以可以假设从最后一个元素向前移动一步会到达第一个元素而第一个元素向后移动一步会到达最后一个元素。数组中的循环由长度为k的下标序列seq标识遵循上述移动规则将导致一组重复下标序列seq[0] - seq[1] - ... - seq[k - 1] - seq[0] - ...所有nums[seq[j]]应当不是全正就是全负k 1如果nums中存在循环返回true否则返回false。思路与上一题相同但是对于循环的定义加了一个额外的条件方向相同在判断的时候注意该点即可。class Solution { public: bool circularArrayLoop(vectorint nums) { int n nums.size(); auto next [](int i){ return ((i nums[i]) % n n) % n; }; for(int i 0; i nums.size(); i){ int slow i, fast i; while(nums[slow] * nums[next(fast)] 0 nums[slow] * nums[next(next(fast))] 0){ // 确保同向 slow next(slow); fast next(next(fast)); if(slow next(slow)) break; // 防止自环 if(slow fast) return 1; } } return 0; } };