链表（典型算法思想）—— OJ例题算法解析思路

目录

一、2. 两数相加 - 力扣（LeetCode）

算法代码： 

1. 初始化

2. 遍历链表并相加

3. 返回结果

举例说明

二、24. 两两交换链表中的节点 - 力扣（LeetCode）

算法代码： 

代码思路

举例说明

初始状态

第一次交换

第二次交换

最终结果

三、143. 重排链表 - 力扣（LeetCode） 

算法代码： 

代码思路

举例说明

初始状态

1. 找到中间节点

2. 逆序后半部分链表

3. 合并两个链表

最终结果

代码总结

执行步骤总结

四、23. 合并 K 个升序链表 - 力扣（LeetCode）

解法一：算法代码（利用堆） 

代码思路

举例说明

初始状态

执行过程

最终结果

代码总结

执行步骤总结

解法二：算法代码（递归/分治）

代码分析

1. 类的结构

2. 主函数 - mergeKLists

3. 分治法 - merge

4. 平分数组与递归

5. 合并两个有序链表 - mergeTowList

6. 合并过程

7. 合并逻辑

8. 处理剩余节点

举例说明

合并过程

五、25. K 个一组翻转链表 - 力扣（LeetCode） 

算法代码： 

代码分析

1. 链表节点结构定义

2. 主函数 - reverseKGroup

3. 逆序过程

4. 处理不需要翻转的部分

举例说明

处理过程

总结

一、2. 两数相加 - 力扣（LeetCode）

算法代码： 

/*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *cur1 = l1, *cur2 = l2;ListNode* newhead = new ListNode(0); // 创建⼀个虚拟头结点，记录最终结果ListNode* prev = newhead;            // 尾指针int t = 0;                           // 记录进位while (cur1 || cur2 || t) {// 先加上第⼀个链表if (cur1) {t += cur1->val;cur1 = cur1->next;}// 加上第⼆个链表if (cur2) {t += cur2->val;cur2 = cur2->next;}prev->next = new ListNode(t % 10);prev = prev->next;t /= 10;}prev = newhead->next;delete newhead;return prev;}
};

1. 初始化

  • 创建两个指针 cur1 和 cur2，分别指向两个链表的头节点 l1 和 l2。

  • 创建一个虚拟头节点 newhead，用于记录最终的结果链表。这个虚拟头节点的作用是简化链表操作，避免处理头节点的特殊情况。

  • 创建一个尾指针 prev，指向当前结果链表的最后一个节点。

  • 初始化一个变量 t，用于记录进位。

2. 遍历链表并相加

  • 使用 while 循环遍历两个链表，直到两个链表都遍历完且没有进位为止。

  • 在循环中：

    • 如果 cur1 不为空，将 cur1 的值加到 t 上，并将 cur1 指向下一个节点。

    • 如果 cur2 不为空，将 cur2 的值加到 t 上，并将 cur2 指向下一个节点。

    • 将 t % 10 的值作为新节点的值，并将其添加到结果链表的末尾。

    • 更新 prev 指针，使其指向新添加的节点。

    • 更新 t 为 t / 10，即计算进位。

3. 返回结果

  • 循环结束后，结果链表的头节点是 newhead->next。

  • 删除虚拟头节点 newhead，避免内存泄漏。

  • 返回结果链表的头节点。

举例说明

假设有两个链表 l1 和 l2，分别表示数字 342 和 465，即：

  • l1: 2 -> 4 -> 3

  • l2: 5 -> 6 -> 4

按照代码的逻辑，相加过程如下：

  1. 初始化:

    • cur1 指向 2，cur2 指向 5。

    • newhead 是一个虚拟头节点，prev 指向 newhead。

    • t = 0。

  2. 第一次循环:

    • t = 0 + 2 + 5 = 7。

    • 创建新节点 7，prev->next 指向 7，prev 指向 7。

    • t = 7 / 10 = 0。

    • cur1 指向 4，cur2 指向 6。

  3. 第二次循环:

    • t = 0 + 4 + 6 = 10。

    • 创建新节点 0，prev->next 指向 0，prev 指向 0。

    • t = 10 / 10 = 1。

    • cur1 指向 3，cur2 指向 4。

  4. 第三次循环:

    • t = 1 + 3 + 4 = 8。

    • 创建新节点 8，prev->next 指向 8，prev 指向 8。

    • t = 8 / 10 = 0。

    • cur1 和 cur2 都为 nullptr，循环结束。

  5. 返回结果:

    • 结果链表为 7 -> 0 -> 8，表示数字 807，即 342 + 465 = 807。

二、24. 两两交换链表中的节点 - 力扣（LeetCode）

算法代码： 

/*** 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* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr)return head;ListNode* newHead = new ListNode(0);newHead->next = head;ListNode *prev = newHead, *cur = prev->next, *next = cur->next,*nnext = next->next;while (cur && next) {// 交换结点prev->next = next;next->next = cur;cur->next = nnext;// 修改指针prev = cur; // 注意顺序cur = nnext;if (cur)next = cur->next;if (next)nnext = next->next;}cur = newHead->next;delete newHead;return cur;}
};

代码思路

  1. 检查边界条件：

    • 如果链表为空（head == nullptr）或只有一个节点（head->next == nullptr），直接返回 head，因为不需要交换。

  2. 创建虚拟头节点：

    • 创建一个虚拟头节点 newHead，并将其 next 指向链表的头节点 head。虚拟头节点的作用是简化头节点的交换操作，避免特殊处理。

  3. 初始化指针：

    • prev：指向当前节点对的前一个节点（初始为 newHead）。

    • cur：指向当前节点对中的第一个节点（初始为 head）。

    • next：指向当前节点对中的第二个节点（初始为 cur->next）。

    • nnext：指向 next 的下一个节点（初始为 next->next）。

  4. 遍历链表并交换节点：

    • 使用 while 循环遍历链表，直到 cur 或 next 为空。

    • 在循环中：

      1. 交换节点：

        • 将 prev->next 指向 next。

        • 将 next->next 指向 cur。

        • 将 cur->next 指向 nnext。

      2. 更新指针：

        • 将 prev 指向 cur（当前节点对中的第一个节点）。

        • 将 cur 指向 nnext。

        • 如果 cur 不为空，将 next 指向 cur->next。

        • 如果 next 不为空，将 nnext 指向 next->next。

  5. 返回结果：

    • 将 cur 指向 newHead->next（交换后的链表头节点）。

    • 删除虚拟头节点 newHead，释放内存。

    • 返回 cur（交换后的链表）。

举例说明

假设链表为 1 -> 2 -> 3 -> 4，交换过程如下：

初始状态

  • newHead -> 1 -> 2 -> 3 -> 4

  • prev = newHead

  • cur = 1

  • next = 2

  • nnext = 3

第一次交换

  1. 交换节点：

    • prev->next 指向 2。

    • next->next 指向 1。

    • cur->next 指向 3。

  2. 更新指针：

    • prev = 1。

    • cur = 3。

    • next = 4。

    • nnext = nullptr（因为 next->next 为空）。

第二次交换

  1. 交换节点：

    • prev->next 指向 4。

    • next->next 指向 3。

    • cur->next 指向 nullptr。

  2. 更新指针：

    • prev = 3。

    • cur = nullptr（因为 nnext 为空）。

    • 循环结束。

最终结果

  • 交换后的链表为 2 -> 1 -> 4 -> 3。

  • 删除虚拟头节点 newHead。

  • 返回 2 作为链表的头节点。

三、143. 重排链表 - 力扣（LeetCode） 

算法代码： 

/*** 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:void reorderList(ListNode* head) {// 处理边界情况if (head == nullptr || head->next == nullptr ||head->next->next == nullptr)return;// 1. 找到链表的中间节点 - 快慢双指针（⼀定要画图考虑 slow// 的落点在哪⾥）ListNode *slow = head, *fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}// 2. 把 slow 后⾯的部分给逆序 - 头插法ListNode* head2 = new ListNode(0);ListNode* cur = slow->next;slow->next = nullptr; // 注意把两个链表给断开while (cur) {ListNode* next = cur->next;cur->next = head2->next;head2->next = cur;cur = next;}// 3. 合并两个链表 - 双指针ListNode* ret = new ListNode(0);ListNode* prev = ret;ListNode *cur1 = head, *cur2 = head2->next;while (cur1) {// 先放第⼀个链表prev->next = cur1;cur1 = cur1->next;prev = prev->next;// 再放第⼆个链表if (cur2) {prev->next = cur2;prev = prev->next;cur2 = cur2->next;}}delete head2;delete ret;}
};

代码思路

  1. 处理边界情况：

    • 如果链表为空（head == nullptr）、只有一个节点（head->next == nullptr）或只有两个节点（head->next->next == nullptr），直接返回，因为不需要重排。

  2. 找到链表的中间节点：

    • 使用 快慢双指针：

      • slow 指针每次移动一步。

      • fast 指针每次移动两步。

    • 当 fast 到达链表末尾时，slow 指向链表的中间节点。

    • 将链表从中间节点断开，分为前半部分和后半部分。

  3. 逆序后半部分链表：

    • 使用 头插法 将后半部分链表逆序：

      • 创建一个虚拟头节点 head2。

      • 遍历后半部分链表，将每个节点插入到 head2 的后面。

    • 最终，head2->next 指向逆序后的后半部分链表。

  4. 合并两个链表：

    • 使用 双指针 将前半部分链表和逆序后的后半部分链表合并：

      • cur1 指向前半部分链表的头节点。

      • cur2 指向逆序后的后半部分链表的头节点。

      • 依次交替连接两个链表的节点。

    • 最终，链表被重排为所需顺序。

  5. 释放临时节点：

    • 删除虚拟头节点 head2 和 ret，释放内存。

举例说明

假设链表为 1 -> 2 -> 3 -> 4 -> 5，重排过程如下：

初始状态

  • 链表：1 -> 2 -> 3 -> 4 -> 5。

1. 找到中间节点

  • slow 指向 3，fast 指向 5。

  • 将链表从 3 断开：

    • 前半部分：1 -> 2 -> 3。

    • 后半部分：4 -> 5。

2. 逆序后半部分链表

  • 逆序后的后半部分链表：5 -> 4。

3. 合并两个链表

  • 交替连接节点：

    • 1 -> 5 -> 2 -> 4 -> 3。

最终结果

  • 重排后的链表为 1 -> 5 -> 2 -> 4 -> 3。

代码总结

  1. 快慢双指针：

    • 用于找到链表的中间节点，确保链表被正确分为两部分。

  2. 头插法逆序链表：

    • 将后半部分链表逆序，便于后续合并。

  3. 双指针合并链表：

    • 交替连接两个链表的节点，完成重排。

  4. 边界条件处理：

    • 确保代码在链表节点数较少时也能正常运行。

执行步骤总结

  1. 找到中间节点并断开链表。

  2. 逆序后半部分链表。

  3. 合并前半部分和逆序后的后半部分链表。

  4. 释放临时节点，返回重排后的链表。

四、23. 合并 K 个升序链表 - 力扣（LeetCode）

解法一：算法代码（利用堆） 

/*** 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 {struct cmp {bool operator()(const ListNode* l1, const ListNode* l2) {return l1->val > l2->val;}};public:ListNode* mergeKLists(vector<ListNode*>& lists) {// 创建⼀个⼩根堆priority_queue<ListNode*, vector<ListNode*>, cmp> heap;// 让所有的头结点进⼊⼩根堆for (auto l : lists)if (l)heap.push(l);// 合并 k 个有序链表ListNode* ret = new ListNode(0);ListNode* prev = ret;while (!heap.empty()) {ListNode* t = heap.top();heap.pop();prev->next = t;prev = t;if (t->next)heap.push(t->next);}prev = ret->next;delete ret;return prev;}
};

代码思路

  1. 定义小根堆的比较器：

    • 使用 struct cmp 定义一个小根堆的比较器，确保堆顶始终是最小的节点。

  2. 初始化小根堆：

    • 创建一个优先队列 heap，用于存储所有链表的当前节点。

    • 将所有链表的头节点加入小根堆（如果链表不为空）。

  3. 合并 K 个有序链表：

    • 创建一个虚拟头节点 ret，用于简化结果链表的构建。

    • 使用指针 prev 指向结果链表的最后一个节点。

    • 循环从堆中取出最小的节点 t，并将其连接到结果链表中。

    • 如果 t->next 不为空，将 t->next 加入小根堆。

    • 重复上述步骤，直到小根堆为空。

  4. 返回结果链表：

    • 返回 ret->next，即合并后的有序链表的头节点。

    • 删除虚拟头节点 ret，释放内存。

举例说明

假设有以下 3 个有序链表：

  • 链表 1：1 -> 4 -> 5

  • 链表 2：1 -> 3 -> 4

  • 链表 3：2 -> 6

初始状态

  • 小根堆中包含所有链表的头节点：[1, 1, 2]。

执行过程

  1. 第一次循环：

    • 取出堆顶节点 1（来自链表 1 或链表 2）。

    • 将 1 连接到结果链表。

    • 将 1->next（4 或 3）加入小根堆。

    • 堆状态：[1, 2, 3] 或 [1, 2, 4]。

  2. 第二次循环：

    • 取出堆顶节点 1（来自另一个链表）。

    • 将 1 连接到结果链表。

    • 将 1->next（3 或 4）加入小根堆。

    • 堆状态：[2, 3, 4]。

  3. 第三次循环：

    • 取出堆顶节点 2（来自链表 3）。

    • 将 2 连接到结果链表。

    • 将 2->next（6）加入小根堆。

    • 堆状态：[3, 4, 6]。

  4. 第四次循环：

    • 取出堆顶节点 3（来自链表 2）。

    • 将 3 连接到结果链表。

    • 将 3->next（4）加入小根堆。

    • 堆状态：[4, 4, 6]。

  5. 第五次循环：

    • 取出堆顶节点 4（来自链表 1 或链表 2）。

    • 将 4 连接到结果链表。

    • 将 4->next（5 或 nullptr）加入小根堆（如果存在）。

    • 堆状态：[4, 5, 6]。

  6. 第六次循环：

    • 取出堆顶节点 4（来自另一个链表）。

    • 将 4 连接到结果链表。

    • 将 4->next（nullptr）不加入小根堆。

    • 堆状态：[5, 6]。

  7. 第七次循环：

    • 取出堆顶节点 5（来自链表 1）。

    • 将 5 连接到结果链表。

    • 将 5->next（nullptr）不加入小根堆。

    • 堆状态：[6]。

  8. 第八次循环：

    • 取出堆顶节点 6（来自链表 3）。

    • 将 6 连接到结果链表。

    • 堆为空，循环结束。

最终结果

  • 合并后的链表为：1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6。

代码总结

  1. 小根堆的作用：

    • 小根堆用于高效地找到当前最小的节点，确保每次都能将最小的节点连接到结果链表中。

  2. 虚拟头节点的使用：

    • 虚拟头节点 ret 简化了结果链表的构建过程。

  3. 时间复杂度：

    • 假设 K 是链表的数量，N 是所有链表的总节点数。

    • 每个节点被插入和弹出小根堆一次，时间复杂度为 O(N log K)。

  4. 空间复杂度：

    • 小根堆最多存储 K 个节点，空间复杂度为 O(K)。

执行步骤总结

  1. 将所有链表的头节点加入小根堆。

  2. 循环从小根堆中取出最小节点，连接到结果链表。

  3. 将取出的节点的下一个节点加入小根堆。

  4. 重复上述步骤，直到小根堆为空。

  5. 返回合并后的有序链表。

 

解法二：算法代码（递归/分治）

/*** 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* mergeKLists(vector<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);}ListNode* merge(vector<ListNode*>& lists, int left, int right) {if (left > right)return nullptr;if (left == right)return lists[left];// 1. 平分数组int mid = left + right >> 1;// [left, mid] [mid + 1, right]// 2. 递归处理左右区间ListNode* l1 = merge(lists, left, mid);ListNode* l2 = merge(lists, mid + 1, right);// 3. 合并两个有序链表return mergeTowList(l1, l2);}ListNode* mergeTowList(ListNode* l1, ListNode* l2) {if (l1 == nullptr)return l2;if (l2 == nullptr)return l1;// 合并两个有序链表ListNode head;ListNode *cur1 = l1, *cur2 = l2, *prev = &head;head.next = nullptr;while (cur1 && cur2) {if (cur1->val <= cur2->val) {prev = prev->next = cur1;cur1 = cur1->next;} else {prev = prev->next = cur2;cur2 = cur2->next;}}if (cur1)prev->next = cur1;if (cur2)prev->next = cur2;return head.next;}
};

代码分析

1. 类的结构
// 链表节点结构
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) {}
};

  • ListNode 是单链表节点的定义，包含一个整数值 val 和指向下一个节点的指针 next。

2. 主函数 - mergeKLists
ListNode* mergeKLists(vector<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);
}

  • mergeKLists 函数接受一个链表数组 lists，调用 merge 函数来合并这些链表，传入左边界和右边界（0 和 lists.size() - 1）。

3. 分治法 - merge
ListNode* merge(vector<ListNode*>& lists, int left, int right) {if (left > right)return nullptr; // 边界情况if (left == right)return lists[left]; // 只有一个链表时返回该链表

  • merge 函数通过递归将链表数组分成两半，继续合并，直到每个子数组只包含一个链表。

  • 如果 left 大于 right，则返回 nullptr；如果 left 等于 right，则返回对应的链表。

4. 平分数组与递归
int mid = left + right >> 1; // 平分数组
ListNode* l1 = merge(lists, left, mid); // 合并左半部分
ListNode* l2 = merge(lists, mid + 1, right); // 合并右半部分

  • 使用索引 mid 将链表数组平分，分别递归调用 merge 函数处理左半部分和右半部分。

5. 合并两个有序链表 - mergeTowList
return mergeTowList(l1, l2);

  • 在左右两部分排序完成后，调用 mergeTowList 函数合并这两个有序链表。

6. 合并过程
ListNode* mergeTowList(ListNode* l1, ListNode* l2) {if (l1 == nullptr)return l2; // 如果 l1 为空，返回 l2if (l2 == nullptr)return l1; // 如果 l2 为空，返回 l1

  • mergeTowList 函数用于合并两个单独的有序链表。

  • 首先处理边界情况，如果某个链表为空，直接返回另一个链表。

7. 合并逻辑
ListNode head;
ListNode *cur1 = l1, *cur2 = l2, *prev = &head;
head.next = nullptr;
while (cur1 && cur2) {if (cur1->val <= cur2->val) {prev = prev->next = cur1; // 将较小的节点加入合并链表cur1 = cur1->next;} else {prev = prev->next = cur2;cur2 = cur2->next;}
}

  • 使用两个指针 cur1 和 cur2 遍历链表 l1 和 l2，通过比较值将较小的节点添加到新的合并链表中，并移动相应的指针。

  • prev 指向合并后的链表的最后一个节点，初始时指向一个虚拟的头节点 head。

8. 处理剩余节点
if (cur1)prev->next = cur1; // 如果 l1 有剩余，连接到合并链表
if (cur2)prev->next = cur2; // 如果 l2 有剩余，连接到合并链表
return head.next; // 返回合并后的链表

  • 如果 cur1 或 cur2 中还有未遍历的节点，将其连接到合并链表的末尾。

  • 返回 head.next，即合并后链表的头节点。

举例说明

假设我们有三个链表如下：

  • 链表 1: 1 -> 4 -> 5

  • 链表 2: 1 -> 3 -> 4

  • 链表 3: 2 -> 6

合并过程

  1. 初始调用:

    mergeKLists([{1, 4, 5}, {1, 3, 4}, {2, 6}])

    • 调用 merge，此时 left = 0, right = 2，进行分割。

  2. 第一次分割:

    • 中间索引 mid = 1。分为 [0, 1] 和 [2]。

    • 对 [0, 1] 继续分割。

  3. 第二次分割:

    • 对 [0, 1]，中间索引 mid = 0，分为 [0] 和 [1]。

    • 递归返回链表 1 和链表 2。

  4. 合并链表 1 和 链表 2:

    • 合并结果为: 1 -> 1 -> 3 -> 4 -> 4 -> 5。

  5. 合并结果与链表 3:

    • 最后调用 mergeTowList 合并结果与链表 3。

    • 合并后的最终结果为: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6。

五、25. K 个一组翻转链表 - 力扣（LeetCode） 

算法代码： 

/*** 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) {// 1. 先求出需要逆序多少组int n = 0;ListNode* cur = head;while (cur) {cur = cur->next;n++;}n /= k;// 2. 重复 n 次：⻓度为 k 的链表的逆序即可ListNode* newHead = new ListNode(0);ListNode* prev = newHead;cur = head;for (int i = 0; i < n; i++) {ListNode* tmp = cur;for (int j = 0; j < k; j++) {ListNode* next = cur->next;cur->next = prev->next;prev->next = cur;cur = next;}prev = tmp;}// 把不需要翻转的接上prev->next = cur;cur = newHead->next;delete newHead;return cur;}
};

代码分析

1. 链表节点结构定义
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) {}
};

  • ListNode 是单链表节点的定义，包含一个整数值 val 和指向下一个节点的指针 next。

2. 主函数 - reverseKGroup
ListNode* reverseKGroup(ListNode* head, int k) {// 1. 先求出需要逆序多少组int n = 0;ListNode* cur = head;while (cur) {cur = cur->next;n++;}n /= k; // 需要逆序的完整组数

  • 该函数接受链表头节点 head 和一个整数 ( k ) 作为输入。

  • 首先，计算链表的长度 ( n )，并通过 n /= k 计算需要逆序的完整组数。

3. 逆序过程
ListNode* newHead = new ListNode(0); // 创建一个虚拟头节点
ListNode* prev = newHead; // prev 指向新链表的尾部
cur = head; // cur 指向原链表的头
for (int i = 0; i < n; i++) {ListNode* tmp = cur; // 暂存当前组的头节点for (int j = 0; j < k; j++) {ListNode* next = cur->next; // 暂存下一个节点cur->next = prev->next; // 将当前节点插入到 prev 后面prev->next = cur; // 更新 prevcur = next; // 移动到下一个节点}prev = tmp; // 更新 prev 为当前组的头节点
}

  • 创建一个虚拟头节点 newHead，方便处理链表的插入和返回。

  • 使用 prev 指针来构建新的链表，初始时指向 newHead。

  • 通过一个外层循环遍历需要逆序的组，每次逆序 ( k ) 个节点。

  • 内层循环负责逆序当前 ( k ) 个节点。具体步骤为：

    • 暂存当前节点的下一个节点 next。

    • 将当前节点 cur 插入到 prev 后面，使得 cur 成为逆序链表的一部分。

    • 更新 cur 指向下一节点。

4. 处理不需要翻转的部分
// 把不需要翻转的接上
prev->next = cur;
cur = newHead->next; // 更新 cur 为新的头节点
delete newHead; // 删除虚拟头节点
return cur; // 返回新的头节点

  • 当所有需要翻转的组都处理完后，将不需要翻转的部分直接连接到 prev 的后面。

  • 更新 cur 为新链表的头节点，删除虚拟头节点 newHead，并返回链表的新头节点。

举例说明

假设有一个链表如下：

  • 输入链表: 1 -> 2 -> 3 -> 4 -> 5

  • k = 2

处理过程

  1. 计算链表长度:

    • 链表长度 ( n = 5 )，计算得到 ( n / k = 2 )。因此，需要逆序 2 组。

  2. 第一次逆序:

    • 当前节点 cur 指向 1，暂存为 tmp。

    • 逆序 2 个节点：

      • 1 -> 2 当前为: 2 -> 1 -> (后续)

      • 2 -> 3 更新: 1 -> 2 -> (后续)

      • 逆序后链表: 2 -> 1 (指向 3)

  3. 第二次逆序:

    • cur 现在指向 3，暂存为 tmp。

    • 逆序 2 个节点：

      • 3 -> 4 当前为: 4 -> 3 -> (后续)

      • 3 -> 5 更新: 4 -> 3 -> (后续)

      • 逆序后链表: 4 -> 3 (指向 5)

  4. 处理剩余节点:

    • 此时 cur 指向 5，prev 指向 3，将 5 直接连接到最后：

    • 最终链表为：2 -> 1 -> 4 -> 3 -> 5

总结

  • 最终输出的链表是：2 -> 1 -> 4 -> 3 -> 5。

  • 当链表的节点数不足 ( k ) 时（例如以下情况1 -> 2 -> 3 -> 4 -> 5 -> 6，当 ( k = 4 ) 时），只会逆序前 4 个节点，后面的节点保持原顺序，结果为：4 -> 3 -> 2 -> 1 -> 5 -> 6。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/18198.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

twisted实现MMORPG 游戏数据库操作封装设计与实现

twisted实现MMORPG 游戏数据库操作封装设计与实现

在设计 MMORPG&#xff08;大规模多人在线角色扮演游戏&#xff09;时&#xff0c;数据库系统是游戏架构中至关重要的一部分。数据库不仅承担了游戏中各种数据&#xff08;如玩家数据、物品数据、游戏世界状态等&#xff09;的存储和管理任务&#xff0c;还必须高效地支持并发访…
阅读更多...
lvsDR模式实现

lvsDR模式实现

LVS DR模式与NAT模式的优缺点&#xff1a; NAT&#xff1a;优点&#xff1a;配置简单&#xff0c;所需网络环境简单&#xff0c;访问流量的出入都经过LVS服务器&#xff0c;控制流量简单&#xff0c; 缺点&#xff1a;由于访问流量的出入都会经过LVS服务器&#xff0c;所以LVS…
阅读更多...
闭源大语言模型的怎么增强:提示工程 检索增强生成 智能体

闭源大语言模型的怎么增强:提示工程 检索增强生成 智能体

闭源大语言模型的怎么增强 提示工程 检索增强生成 智能体 核心原理 提示工程：通过设计和优化提示词，引导大语言模型进行上下文学习和分解式思考，激发模型自身的思维和推理能力，使模型更好地理解和生成文本，增强其泛用性和解决问题的能力。检索增强生成：结合检索的准确…
阅读更多...
【快速幂算法】快速幂算法讲解及C语言实现（递归实现和非递归实现，附代码）

【快速幂算法】快速幂算法讲解及C语言实现（递归实现和非递归实现，附代码）

快速幂算法 快速幂算法可用分治法实现 不难看出&#xff0c;对任意实数a和非负整数n&#xff0c;有&#xff1a; a n { 1 , n 0 , a ≠ 0 0 , a 0 ( a n 2 ) 2 , n > 0 , n 为偶数 ( a n 2 ) 2 ∗ a , n > 0 , n 为奇数 a^n \begin{cases} 1, & n 0, a\neq 0…
阅读更多...
大数据SQL调优专题——Hive执行原理

大数据SQL调优专题——Hive执行原理

引入 Apache Hive 是基于Hadoop的数据仓库工具&#xff0c;它可以使用SQL来读取、写入和管理存在分布式文件系统中的海量数据。在Hive中&#xff0c;HQL默认转换成MapReduce程序运行到Yarn集群中&#xff0c;大大降低了非Java开发者数据分析的门槛&#xff0c;并且Hive提供命令…
阅读更多...
30天开发操作系统 第 20 天 -- API

30天开发操作系统 第 20 天 -- API

前言 大家早上好&#xff0c;今天我们继续努力哦。 昨天我们已经实现了应用程序的运行, 今天我们来实现由应用程序对操作系统功能的调用(即API, 也叫系统调用)。 为什么这样的功能称为“系统调用”(system call)呢&#xff1f;因为它是由应用程序来调用(操作)系统中的功能来完…
阅读更多...
UE5.2后 Bake Out Materials失效

UE5.2后 Bake Out Materials失效

这个问题出现在5.3&#xff0c;5.4&#xff0c;5.5没有测试 烘焙贴图后会找不到贴图位置&#xff0c; 这个是5.2的正常状态 默认是生成在模型当前目录里&#xff0c;包括新的材质 但是这个bug会让材质和贴图都消失&#xff0c;无法定位 暂时没有办法解决&#xff0c;等官方 …
阅读更多...
macOS部署DeepSeek-r1

macOS部署DeepSeek-r1

好奇&#xff0c;跟着网友们的操作试了一下 网上方案很多&#xff0c;主要参考的是这篇 DeepSeek 接入 PyCharm&#xff0c;轻松助力编程_pycharm deepseek-CSDN博客 方案是&#xff1a;PyCharm CodeGPT插件 DeepSeek-r1:1.5b 假设已经安装好了PyCharm PyCharm: the Pyth…
阅读更多...
架构设计系列（二）：CI/CD

架构设计系列（二）：CI/CD

一、概述 CI/CD 是 持续集成&#xff08;Continuous Integration&#xff09; 和 持续交付/持续部署&#xff08;Continuous Delivery/Continuous Deployment&#xff09; 的缩写&#xff0c;是现代软件开发中的一套核心实践和工具链&#xff0c;旨在提高软件交付的效率、质量…
阅读更多...
Windows 11 搭建私有知识库（docker、dify、deepseek、ollama）

Windows 11 搭建私有知识库（docker、dify、deepseek、ollama）

一、操作系统信息 版本 Windows 11 家庭中文版 版本号 23H2 安装日期 ‎2023/‎8/‎21 操作系统版本 22631.4460二、搭建思路 ollama拉取deepseek、bge-m3模型docker拉取dify的镜像dify链接ollama使用模型&#xff0c;并上传文件搭建知识库&#xff0c;创建应用 三、搭建步骤…
阅读更多...
本地部署DeepSeek摆脱服务器繁忙

本地部署DeepSeek摆脱服务器繁忙

由于图片和格式解析问题&#xff0c;可前往 阅读原文 最近DeepSeek简直太火了&#xff0c;频频霸榜热搜打破春节的平静&#xff0c;大模型直接开源让全球科技圈都为之震撼&#xff01;再次证明了中国AI的换道超车与崛起 DeepSeek已经成了全民ai&#xff0c;使用量也迅速上去了…
阅读更多...
‌CBA认证‌（业务架构师认证）简介---适用人群、考试内容与形式、含金量与职业前景，以及‌CBA、TOGAF认证对比表格

‌CBA认证‌（业务架构师认证）简介---适用人群、考试内容与形式、含金量与职业前景，以及‌CBA、TOGAF认证对比表格

‌CBA认证‌&#xff0c;即业务架构师认证&#xff08;Certified Business Architect&#xff0c;CBA&#xff09;&#xff0c;是由业务架构师协会&#xff08;Business Architecture Institute&#xff09;推出的一项国际认证计划。该认证旨在评估和认证业务架构师的专业能力和…
阅读更多...
保姆级GitHub大文件（100mb-2gb）上传教程

保姆级GitHub大文件（100mb-2gb）上传教程

GLF&#xff08;Git Large File Storage&#xff09;安装使用 使用GitHub desktop上传大于100mb的文件时报错 The following files are over 100MB. lf you commit these files, you will no longer beable to push this repository to GitHub.com.term.rarWe recommend you a…
阅读更多...
使用 Visual Studio Code (VS Code) 开发 Python 图形界面程序

使用 Visual Studio Code (VS Code) 开发 Python 图形界面程序

安装Python、VS Code Documentation for Visual Studio Code Python Releases for Windows | Python.org 更新pip >python.exe -m pip install --upgrade pip Requirement already satisfied: pip in c:\users\xxx\appdata\local\programs\python\python312\lib\site-pa…
阅读更多...
Python的那些事第二十一篇：Python Web开发的“秘密武器”Flask

Python的那些事第二十一篇：Python Web开发的“秘密武器”Flask

基于 Flask 框架的 Python Web 开发研究 摘要 在 Web 开发的江湖里，Python 是一位武林高手，而 Flask 则是它手中那把小巧却锋利的匕首。本文以 Flask 框架为核心，深入探讨了它在 Python Web 开发中的应用。通过幽默风趣的笔触，结合实例和表格，分析了 Flask 的特性、优势以…
阅读更多...
Qt开发①Qt的概念+发展+优点+应用+使用

Qt开发①Qt的概念+发展+优点+应用+使用

目录 1. Qt的概念和发展 1.1 Qt的概念 1.2 Qt 的发展史&#xff1a; 1.3 Qt 的版本 2. Qt 的优点和应用 2.1 Qt 的优点&#xff1a; 2.2 Qt 的应用场景 2.3 Qt 的应用案例 3. 搭建 Qt 开发环境 3.1 Qt 的开发工具 3.2 Qt SDK 的下载和安装 3.3 Qt 环境变量配置和使…
阅读更多...
【第4章：循环神经网络（RNN）与长短时记忆网络（LSTM）— 4.3 RNN与LSTM在自然语言处理中的应用案例】

【第4章：循环神经网络（RNN）与长短时记忆网络（LSTM）— 4.3 RNN与LSTM在自然语言处理中的应用案例】

咱今天来聊聊在人工智能领域里，特别重要的两个神经网络：循环神经网络（RNN）和长短时记忆网络（LSTM），主要讲讲它们在自然语言处理里的应用。你想想，平常咱们用手机和别人聊天、看新闻、听语音助手说话，背后说不定就有 RNN 和 LSTM 在帮忙呢！ 二、RNN 是什么？ （一）…
阅读更多...
DeepSeek应用——与PyCharm的配套使用

DeepSeek应用——与PyCharm的配套使用

目录 一、配置方法 二、使用方法 三、注意事项 1、插件市场无continue插件 2、无结果返回&#xff0c;且在本地模型报错 记录自己学习应用DeepSeek的过程&#xff0c;使用的是自己电脑本地部署的私有化蒸馏模型...... &#xff08;举一反三&#xff0c;这个不单单是可以用…
阅读更多...
国自然地区基金｜影像组学联合病理组学预测进展期胃癌术后预后的研究｜基金申请·25-02-13

国自然地区基金｜影像组学联合病理组学预测进展期胃癌术后预后的研究｜基金申请·25-02-13

小罗碎碎念 今天和大家分享一个国自然地区科学项目&#xff0c;执行年限为2020.01&#xff5e;2023.12&#xff0c;直接费用为34万元。 胃癌在我国发病形势严峻&#xff0c;现有TNM分期预后评估存在局限&#xff0c;难以满足精准医疗需求。本项目运用“医工结合&#xff0c;学科…
阅读更多...
【Java集合一】集合概述

【Java集合一】集合概述

一、集合简介 Java 集合框架&#xff08;Collection Framework&#xff09;是 Java 提供的一组用于存储和操作对象的类和接口集合。这些集合类提供了不同的数据结构&#xff0c;使得数据的管理和操作更加方便和高效。 Java 集合框架提供了各种类型的数据结构&#xff0c;如列…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023