全屏网站 图片优化,中国设计师排名,做得大气的网站,设计公司官网首页目录
一、2. 两数相加 - 力扣#xff08;LeetCode#xff09;
算法代码#xff1a;
1. 初始化
2. 遍历链表并相加
3. 返回结果
举例说明
二、24. 两两交换链表中的节点 - 力扣#xff08;LeetCode#xff09;
算法代码#xff1a;
代码思路
举例说明
初始状…目录
一、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
按照代码的逻辑相加过程如下 初始化: cur1 指向 2cur2 指向 5。 newhead 是一个虚拟头节点prev 指向 newhead。 t 0。 第一次循环: t 0 2 5 7。 创建新节点 7prev-next 指向 7prev 指向 7。 t 7 / 10 0。 cur1 指向 4cur2 指向 6。 第二次循环: t 0 4 6 10。 创建新节点 0prev-next 指向 0prev 指向 0。 t 10 / 10 1。 cur1 指向 3cur2 指向 4。 第三次循环: t 1 3 4 8。 创建新节点 8prev-next 指向 8prev 指向 8。 t 8 / 10 0。 cur1 和 cur2 都为 nullptr循环结束。 返回结果: 结果链表为 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;}
};
代码思路 检查边界条件 如果链表为空head nullptr或只有一个节点head-next nullptr直接返回 head因为不需要交换。 创建虚拟头节点 创建一个虚拟头节点 newHead并将其 next 指向链表的头节点 head。虚拟头节点的作用是简化头节点的交换操作避免特殊处理。 初始化指针 prev指向当前节点对的前一个节点初始为 newHead。 cur指向当前节点对中的第一个节点初始为 head。 next指向当前节点对中的第二个节点初始为 cur-next。 nnext指向 next 的下一个节点初始为 next-next。 遍历链表并交换节点 使用 while 循环遍历链表直到 cur 或 next 为空。 在循环中 交换节点 将 prev-next 指向 next。 将 next-next 指向 cur。 将 cur-next 指向 nnext。 更新指针 将 prev 指向 cur当前节点对中的第一个节点。 将 cur 指向 nnext。 如果 cur 不为空将 next 指向 cur-next。 如果 next 不为空将 nnext 指向 next-next。 返回结果 将 cur 指向 newHead-next交换后的链表头节点。 删除虚拟头节点 newHead释放内存。 返回 cur交换后的链表。 举例说明
假设链表为 1 - 2 - 3 - 4交换过程如下
初始状态 newHead - 1 - 2 - 3 - 4 prev newHead cur 1 next 2 nnext 3
第一次交换 交换节点 prev-next 指向 2。 next-next 指向 1。 cur-next 指向 3。 更新指针 prev 1。 cur 3。 next 4。 nnext nullptr因为 next-next 为空。
第二次交换 交换节点 prev-next 指向 4。 next-next 指向 3。 cur-next 指向 nullptr。 更新指针 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;}
};
代码思路 处理边界情况 如果链表为空head nullptr、只有一个节点head-next nullptr或只有两个节点head-next-next nullptr直接返回因为不需要重排。 找到链表的中间节点 使用 快慢双指针 slow 指针每次移动一步。 fast 指针每次移动两步。 当 fast 到达链表末尾时slow 指向链表的中间节点。 将链表从中间节点断开分为前半部分和后半部分。 逆序后半部分链表 使用 头插法 将后半部分链表逆序 创建一个虚拟头节点 head2。 遍历后半部分链表将每个节点插入到 head2 的后面。 最终head2-next 指向逆序后的后半部分链表。 合并两个链表 使用 双指针 将前半部分链表和逆序后的后半部分链表合并 cur1 指向前半部分链表的头节点。 cur2 指向逆序后的后半部分链表的头节点。 依次交替连接两个链表的节点。 最终链表被重排为所需顺序。 释放临时节点 删除虚拟头节点 head2 和 ret释放内存。 举例说明 假设链表为 1 - 2 - 3 - 4 - 5重排过程如下
初始状态 链表1 - 2 - 3 - 4 - 5。
1. 找到中间节点 slow 指向 3fast 指向 5。 将链表从 3 断开 前半部分1 - 2 - 3。 后半部分4 - 5。
2. 逆序后半部分链表 逆序后的后半部分链表5 - 4。
3. 合并两个链表 交替连接节点 1 - 5 - 2 - 4 - 3。
最终结果 重排后的链表为 1 - 5 - 2 - 4 - 3。 代码总结 快慢双指针 用于找到链表的中间节点确保链表被正确分为两部分。 头插法逆序链表 将后半部分链表逆序便于后续合并。 双指针合并链表 交替连接两个链表的节点完成重排。 边界条件处理 确保代码在链表节点数较少时也能正常运行。 执行步骤总结 找到中间节点并断开链表。 逆序后半部分链表。 合并前半部分和逆序后的后半部分链表。 释放临时节点返回重排后的链表。 四、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(vectorListNode* lists) {// 创建⼀个⼩根堆priority_queueListNode*, vectorListNode*, 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;}
};
代码思路 定义小根堆的比较器 使用 struct cmp 定义一个小根堆的比较器确保堆顶始终是最小的节点。 初始化小根堆 创建一个优先队列 heap用于存储所有链表的当前节点。 将所有链表的头节点加入小根堆如果链表不为空。 合并 K 个有序链表 创建一个虚拟头节点 ret用于简化结果链表的构建。 使用指针 prev 指向结果链表的最后一个节点。 循环从堆中取出最小的节点 t并将其连接到结果链表中。 如果 t-next 不为空将 t-next 加入小根堆。 重复上述步骤直到小根堆为空。 返回结果链表 返回 ret-next即合并后的有序链表的头节点。 删除虚拟头节点 ret释放内存。 举例说明
假设有以下 3 个有序链表 链表 11 - 4 - 5 链表 21 - 3 - 4 链表 32 - 6
初始状态 小根堆中包含所有链表的头节点[1, 1, 2]。
执行过程 第一次循环 取出堆顶节点 1来自链表 1 或链表 2。 将 1 连接到结果链表。 将 1-next4 或 3加入小根堆。 堆状态[1, 2, 3] 或 [1, 2, 4]。 第二次循环 取出堆顶节点 1来自另一个链表。 将 1 连接到结果链表。 将 1-next3 或 4加入小根堆。 堆状态[2, 3, 4]。 第三次循环 取出堆顶节点 2来自链表 3。 将 2 连接到结果链表。 将 2-next6加入小根堆。 堆状态[3, 4, 6]。 第四次循环 取出堆顶节点 3来自链表 2。 将 3 连接到结果链表。 将 3-next4加入小根堆。 堆状态[4, 4, 6]。 第五次循环 取出堆顶节点 4来自链表 1 或链表 2。 将 4 连接到结果链表。 将 4-next5 或 nullptr加入小根堆如果存在。 堆状态[4, 5, 6]。 第六次循环 取出堆顶节点 4来自另一个链表。 将 4 连接到结果链表。 将 4-nextnullptr不加入小根堆。 堆状态[5, 6]。 第七次循环 取出堆顶节点 5来自链表 1。 将 5 连接到结果链表。 将 5-nextnullptr不加入小根堆。 堆状态[6]。 第八次循环 取出堆顶节点 6来自链表 3。 将 6 连接到结果链表。 堆为空循环结束。
最终结果 合并后的链表为1 - 1 - 2 - 3 - 4 - 4 - 5 - 6。 代码总结 小根堆的作用 小根堆用于高效地找到当前最小的节点确保每次都能将最小的节点连接到结果链表中。 虚拟头节点的使用 虚拟头节点 ret 简化了结果链表的构建过程。 时间复杂度 假设 K 是链表的数量N 是所有链表的总节点数。 每个节点被插入和弹出小根堆一次时间复杂度为 O(N log K)。 空间复杂度 小根堆最多存储 K 个节点空间复杂度为 O(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* mergeKLists(vectorListNode* lists) {return merge(lists, 0, lists.size() - 1);}ListNode* merge(vectorListNode* 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(vectorListNode* lists) {return merge(lists, 0, lists.size() - 1);
}mergeKLists 函数接受一个链表数组 lists调用 merge 函数来合并这些链表传入左边界和右边界0 和 lists.size() - 1。
3. 分治法 - merge
ListNode* merge(vectorListNode* 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 为空返回 l1mergeTowList 函数用于合并两个单独的有序链表。 首先处理边界情况如果某个链表为空直接返回另一个链表。
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
合并过程 初始调用: mergeKLists([{1, 4, 5}, {1, 3, 4}, {2, 6}])调用 merge此时 left 0, right 2进行分割。 第一次分割: 中间索引 mid 1。分为 [0, 1] 和 [2]。 对 [0, 1] 继续分割。 第二次分割: 对 [0, 1]中间索引 mid 0分为 [0] 和 [1]。 递归返回链表 1 和链表 2。 合并链表 1 和 链表 2: 合并结果为: 1 - 1 - 3 - 4 - 4 - 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
处理过程 计算链表长度: 链表长度 ( n 5 )计算得到 ( n / k 2 )。因此需要逆序 2 组。 第一次逆序: 当前节点 cur 指向 1暂存为 tmp。 逆序 2 个节点 1 - 2 当前为: 2 - 1 - (后续) 2 - 3 更新: 1 - 2 - (后续) 逆序后链表: 2 - 1 (指向 3) 第二次逆序: cur 现在指向 3暂存为 tmp。 逆序 2 个节点 3 - 4 当前为: 4 - 3 - (后续) 3 - 5 更新: 4 - 3 - (后续) 逆序后链表: 4 - 3 (指向 5) 处理剩余节点: 此时 cur 指向 5prev 指向 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。
