1.k个一组翻转链表
思路分析：我们需要将链表分成若干个长度为 k 的子链表组，逐组进行翻转。若最后一组节点的数量不足 k，则保持原有顺序
-
创建一个虚拟头节点 dummy，以简化边界条件的处理。该节点的 next 指向链表的头节点。通过 dummy 节点，可以轻松连接翻转后的链表和未翻转部分，避免对链表头节点的特殊处理。
-
循环遍历链表：使用while循环不断寻找长度为k的子链表。如果剩余节点不足k，则退出循环。
-
翻转每组节点
- 在找到的一组k个节点中，使用三指针法进行翻转
- prev指针指向当前组后面未翻转部分的第一个节点；
- node指针指向当前组的第一个节点；
- nextNode用于暂存node的下一个节点，以便在翻转过程中不断移动
- 在循环中，逐个节点调整next指针，反转指向关系
-
连接翻转后的节点
- 将翻转后的组连接到preGroupEnd(上一组的尾节点）的next指针上；
- 更新prevGroupEnd为当前组的起始节点，以便为下一组的连接做准备
-
更新当前节点
- 将curr更新为当前组的下一个节点，继续寻找下一组进行翻转。
具体实现代码（详解版）
/*** 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* dummy = new ListNode(0,head);if(!head || k == 1) return head;ListNode* prevGroupEnd = dummy;//保存上一个翻转组的尾部节点ListNode* curr = head;//当前节点while(true){ListNode* groupStart = curr;//当前组的起始节点int count = 0;//检查当前剩余节点是否足够组成一组while(curr && count < k){curr = curr->next;count ++;}//不足k个节点，跳出循环，不再翻转if(count < k) break;//翻转当前的k个节点ListNode* prev = curr;ListNode* node = groupStart;for(int i = 0 ; i < k ; i ++){ListNode* nextNode = node->next;node->next = prev;prev = node;node = nextNode;}//连接上一组和当前组prevGroupEnd->next = prev;//当前组的尾部翻转后变为组的头prevGroupEnd = groupStart;//当前翻转前的头变成了组的尾部curr = groupStart->next;//移动到下一个组的第一个节点}return dummy->next;}
};
- 时间复杂度为 0 ( n ) 0(n) 0(n),空间复杂度为 O ( 1 ) . O(1). O(1).
2.随机链表的复制
思路分析（回溯+哈希表）：可以使用回溯和哈希表的组合方法来实现深拷贝链表。哈希表用于保存原链表节点与其对应的新节点之间的映射关系，从而实现递归回溯创建新节点并设置 next 和 random 指针。
- 递归回溯
- 对于每个节点node，检查是否已经创建了它的副本
- 如果node的副本已经存在（可以在哈希表中找到），则直接返回该副本，避免重复创建；
- 如果node的副本不存在，创建一个新节点并将其加入哈希表，用于后续访问时直接返回；
- 哈希表保存映射关系
- 使用哈希表存储原节点和对应新节点之间的映射关系；
- 通过该映射关系，可以在递归调用中迅速找到原节点对应的新节点，并在处理 next 和 random 指针时避免重复创建。
- 递归创建新节点的 next 和 random 指针：
- 对于新创建的节点，通过递归回溯设置它的 next 和 random 指针，分别指向递归创建的相应位置的节点。
具体实现代码（详解版）：
/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:unordered_map<Node*,Node*> nodeMap;Node* copyRandomList(Node* head) {//哈希表，存储原节点和对应新节点的映射if(!head) return nullptr;//检查哈希表中是否已经存在该节点的副本if(nodeMap.find(head) != nodeMap.end()) return nodeMap[head];//创建新节点并将其添加到哈希表中Node* newNode = new Node(head->val);nodeMap[head] = newNode;//递归设置next和random指针newNode->next = copyRandomList(head->next);newNode->random = copyRandomList(head->random);return newNode;}
};
- 时间复杂度：O(n),n为节点数
- 空间复杂度：O(n),使用哈希表保存节点之间的映射关系。
3.排序链表
思路分析1（先存储再排序）：
- 遍历链表将值存入数组；
- 然后排序数组；
- 将排序后的值更新回链表。
具体实现代码（详解版）：
class Solution {
public:ListNode* sortList(ListNode* head) {ListNode* tmp = head;vector<int> arr;while(tmp) {arr.push_back(tmp -> val);tmp = tmp -> next;}sort(arr.begin(), arr.end());int i;for(i = 0, tmp = head;i < arr.size(), tmp != nullptr; i++, tmp = tmp -> next) {tmp -> val = arr[i];}return head;}
};2.思路分析2（归并排序）
- 递归分割链表
- 使用快慢指针找到链表的中间位置，slow最终停在链表的中点，fast到链表末尾
- 将链表从中间位置断开，形式左右两部分进行递归排序
- 合并两个已排序链表
- 使用辅助函数 mergeTwoLists，按升序合并两个已排序链表。
- dummy 节点帮助简化边界处理逻辑，最终返回 dummy.next 指向合并后的链表。
- 使用归并排序，在链表上实现了稳定且有效的排序。
具体实现代码（详解版）：
/*** 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* sortList(ListNode* head) {// 基本情况：如果链表为空或只有一个节点，则已经有序，直接返回if (!head || !head->next) return head;// 第一步：使用快慢指针将链表分成两半ListNode* slow = head;ListNode* fast = head;ListNode* prev = nullptr;// 使用快慢指针寻找链表的中间节点while (fast && fast->next) {prev = slow;slow = slow->next;fast = fast->next->next;}// 将链表分成两部分prev->next = nullptr;// 递归排序每一半ListNode* left = sortList(head);ListNode* right = sortList(slow);// 合并两个已排序的链表return mergeTwoLists(left, right);}private:// 辅助函数：合并两个已排序的链表ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode dummy(0); // 哑节点，方便操作ListNode* tail = &dummy;// 合并两个链表while (l1 && l2) {if (l1->val < l2->val) {tail->next = l1; // 将 l1 的当前节点连接到合并后的链表中l1 = l1->next; // 移动 l1 到下一个节点} else {tail->next = l2; // 将 l2 的当前节点连接到合并后的链表中l2 = l2->next; // 移动 l2 到下一个节点}tail = tail->next; // 移动 tail 到合并后的链表的最后一个节点}// 将剩余的节点（如果有）连接到合并后的链表中tail->next = l1 ? l1 : l2;return dummy.next; // 返回合并后的链表头节点}
};4.合并4个升序链表
**思路分析1（暴力顺序合并）：**我们可以想到一种最朴素的方法：用一个变量 res 来维护以及合并的链表，第 i 次循环把第 i 个链表和 res 合并，答案保存到 res 中。
具体实现代码（详解版）：
/*** 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:// 合并 k 个已排序链表ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode* res = nullptr; // 初始化合并后的链表为 nullptr// 遍历每一个链表，并依次合并for(size_t i = 0; i < lists.size(); i++) {res = mergeTwoLists(res, lists[i]); // 合并当前链表与已合并的链表}return res; // 返回合并后的链表}private:// 辅助函数：合并两个已排序的链表ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode dummy(0); // 哑节点，方便操作，避免处理空链表时的特殊情况ListNode* tail = &dummy; // 指向合并链表的最后一个节点// 合并两个链表while (l1 && l2) { // 当两个链表都不为空时if (l1->val < l2->val) {tail->next = l1; // 将 l1 的当前节点连接到合并后的链表中l1 = l1->next; // 移动 l1 到下一个节点} else {tail->next = l2; // 将 l2 的当前节点连接到合并后的链表中l2 = l2->next; // 移动 l2 到下一个节点}tail = tail->next; // 移动 tail 到合并后的链表的最后一个节点}// 将剩余的节点（如果有）连接到合并后的链表中tail->next = l1 ? l1 : l2; // 如果 l1 还有剩余，则连接 l1，反之连接 l2return dummy.next; // 返回合并后的链表头节点}
};思路分析2（使用优先队列）：
- 使用优先队列：使用优先队列（最小堆）来保持每个链表的头节点，确保我们总是可以快速获取当前最小的节点。
- 初始化优先队列：
- 将每个链表的头节点放入优先队列中。这样，优先队列中将始终保持所有待处理的节点，并且可以通过堆的特性来获取最小的节点
- 合并链表
- 创建一个虚拟头节点 dummy，用于方便处理合并链表的操作。通过一个 tail 指针来跟踪合并链表的最后一个节点。
- 反复从优先队列中取出最小的节点，并将其添加到合并链表中。
- 如果取出的节点有下一个节点，则将其下一个节点也放入优先队列中。这样，优先队列中始终保留当前各链表的待处理节点。
- 返回结果
- 合并完成之和，返回虚拟头节点 dummy 的下一个节点，即合并链表的头节点
具体实现代码（详解版）：
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {// 定义一个优先队列，按节点值排序auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> minHeap(cmp);// 将每个链表的头节点放入优先队列中for (ListNode* list : lists) {if (list) {minHeap.push(list);}}// 创建一个虚拟头节点，以便于处理合并链表ListNode dummy(0);ListNode* tail = &dummy;// 合并过程while (!minHeap.empty()) {// 取出最小的节点ListNode* minNode = minHeap.top();minHeap.pop();// 将该节点连接到合并链表中tail->next = minNode;tail = tail->next;// 如果该节点有下一个节点，则将其加入优先队列if (minNode->next) {minHeap.push(minNode->next);}}return dummy.next; // 返回合并后的链表头节点}
};
5.LRU缓存
具体实现代码（详解版）：
// 定义双向链表节点结构体
struct DLinkedNode {int key, value; // 节点的键和值DLinkedNode* prev; // 指向前一个节点的指针DLinkedNode* next; // 指向下一个节点的指针// 默认构造函数DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}// 带参数的构造函数DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};// 定义 LRUCache 类
class LRUCache {
private:unordered_map<int, DLinkedNode*> cache; // 哈希表，存储键与双向链表节点的映射DLinkedNode* head; // 伪头部节点DLinkedNode* tail; // 伪尾部节点int size; // 当前缓存的大小int capacity; // 缓存的最大容量public:// 构造函数，初始化缓存容量LRUCache(int _capacity): capacity(_capacity), size(0) {// 创建伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head->next = tail; // 头部的下一个指向尾部tail->prev = head; // 尾部的前一个指向头部}// 获取缓存中键对应的值int get(int key) {if (!cache.count(key)) {return -1; // 如果键不存在，返回 -1}// 如果键存在，找到对应节点并移动到头部DLinkedNode* node = cache[key];moveToHead(node); // 将该节点移动到链表头部return node->value; // 返回节点的值}// 插入或更新缓存中的键值对void put(int key, int value) {if (!cache.count(key)) { // 如果键不存在// 创建一个新的节点DLinkedNode* node = new DLinkedNode(key, value);// 将节点添加到哈希表cache[key] = node;// 添加到双向链表的头部addToHead(node);++size; // 增加缓存大小// 如果超出容量，删除双向链表的尾部节点if (size > capacity) {DLinkedNode* removed = removeTail(); // 删除尾部节点cache.erase(removed->key); // 从哈希表中移除delete removed; // 释放内存--size; // 减小缓存大小}} else { // 如果键已存在DLinkedNode* node = cache[key];node->value = value; // 更新节点的值moveToHead(node); // 将该节点移动到链表头部}}// 将节点添加到双向链表的头部void addToHead(DLinkedNode* node) {node->prev = head; // 设置节点的前驱为头部node->next = head->next; // 设置节点的后继为头部的下一个节点head->next->prev = node; // 将头部的下一个节点的前驱指向新节点head->next = node; // 将头部的下一个节点指向新节点}// 从双向链表中移除指定节点void removeNode(DLinkedNode* node) {node->prev->next = node->next; // 将前驱节点的后继指向当前节点的后继node->next->prev = node->prev; // 将后继节点的前驱指向当前节点的前驱}// 将指定节点移动到双向链表的头部void moveToHead(DLinkedNode* node) {removeNode(node); // 移除节点addToHead(node); // 将节点添加到头部}// 移除双向链表的尾部节点DLinkedNode* removeTail() {DLinkedNode* node = tail->prev; // 获取尾部前一个节点removeNode(node); // 从链表中移除该节点return node; // 返回被移除的节点}
};
