网站建设市场数据分析,外贸网站建设系统,无限个网站虚拟空间,个人如何做问答类网站本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个头结点为 head 的单链表和一个整数 k 请你设计一个算法将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。
这 k 个部分应该按照在链表中出现的顺序排列并且排在前面的部分的长度应该大于或等于排在后面的长度。
返回一个由上述 k 部分组成的数组。
示例 1
输入head [1,2,3], k 5
输出[[1],[2],[3],[],[]]
解释
第一个元素 output[0] 为 output[0].val 1 output[0].next null 。
最后一个元素 output[4] 为 null 但它作为 ListNode 的字符串表示是 [] 。示例 2
输入head [1,2,3,4,5,6,7,8,9,10], k 3
输出[[1,2,3,4],[5,6,7],[8,9,10]]
解释
输入被分成了几个连续的部分并且每部分的长度相差不超过 1 。前面部分的长度大于等于后面部分的长度。提示
链表中节点的数目在范围 [0, 1000]0 Node.val 10001 k 50 解法 双重循环
题目要求将给定的链表分隔成 k k k 个连续的部分。由于分隔成的每个部分的长度和原始链表的长度有关因此需要首先遍历链表得到链表的长度 n n n 。
得到链表的长度 n n n 之后记 quotient ⌊ n k ⌋ \textit{quotient} \Big\lfloor \dfrac{n}{k} \Big\rfloor quotient⌊kn⌋ remainder n m o d k \textit{remainder} n \bmod k remaindernmodk 则在分隔成的 k k k 个部分中前 r e m a i n d e r remainder remainder 个部分的长度各为 q u o t i e n t 1 quotient1 quotient1 其余每个部分的长度各为 quotient \textit{quotient} quotient 。
分隔链表时从链表的头结点开始遍历记当前结点为 c u r r curr curr对于每个部分进行如下操作
将 c u r r curr curr 作为当前部分的头结点计算当前部分的长度 p a r t S i z e partSize partSize将 c u r r curr curr 向后移动 p a r t S i z e partSize partSize 步则 c u r r curr curr 为当前部分的尾结点当 c u r r curr curr 到达当前部分的尾结点时需要拆分 c u r r curr curr 和后面一个结点之间的连接关系在拆分之前需要存储 c u r r curr curr 的后一个结点 n e x t next next令 c u r r curr curr 的 n e x t next next 指针指向 n u l l null null完成 c u r r curr curr 和 n e x t next next 的拆分将 n e x t next next 赋值给 c u r r curr curr。
完成上述操作之后即得到分隔链表后的一个部分。重复上述操作直到分隔出 k k k 个部分或者链表遍历结束即 c u r r curr curr 指向 n u l l null null 。
class Solution {
public:vectorListNode* splitListToParts(ListNode* head, int k) {int n 0;ListNode *temp head;while (temp) { n; temp temp-next; }int quotient n / k, remainder n % k;vectorListNode* parts(k, nullptr);ListNode* curr head;for (int i 0; i k curr; i) {parts[i] curr;int partSize quotient (i remainder ? 1 : 0);for (int j 1; j partSize; j) curr curr-next;ListNode *next curr-next;curr-next nullptr;curr next;}return parts;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) 其中 n n n 是链表的长度。需要遍历链表两次得到链表的长度和分隔链表。空间复杂度 O ( 1 ) O(1) O(1) 。只使用了常量的额外空间注意返回值不计入空间复杂度。
