LeetCode 725. 分隔链表
难度:middle\color{orange}{middle}middle
题目描述
给你一个头结点为 headheadhead 的单链表和一个整数 kkk ,请你设计一个算法将链表分隔为 kkk 个连续的部分。
每部分的长度应该尽可能的相等:任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。
这 kkk 个部分应该按照在链表中出现的顺序排列,并且排在前面的部分的长度应该大于或等于排在后面的长度。
返回一个由上述 kkk 部分组成的数组。
示例 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, 1000][0,1000]
- 0<=Node.val<=10000 <= Node.val <= 10000<=Node.val<=1000
- 1<=k<=501 <= k <= 501<=k<=50
算法
(链表操作、模拟)
- 首先求出链表的长度
n
- 在每个分隔的链表求各自的长度
n / k
如果此时n / k
不是一个整数,那么n % k
就会存在余数,从前往后依次让分隔的链表长度 + 1 - 分隔链表的长度为
len
那么循环len-1
次就可以走到该链表的最后一个位置。 - 在拆分之前需要存储
p
的后一个结点next
; - 令
p
的next
指针指向null
,完成p
和next
的拆分; - 将
next
赋值给p
。
复杂度分析
-
时间复杂度:O(n)O(n)O(n),其中 nnn 是链表的长度。
-
空间复杂度 : O(1)O(1)O(1)
C++ 代码
/*** 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:vector<ListNode*> splitListToParts(ListNode* head, int k) {int n = 0;for (auto p = head; p; p = p->next) n ++;vector<ListNode*> res;auto p = head;for (int i = 0; i < k; i ++) {//求出一段有多长int len = n / k;//如果不能整除,判断前面有几部分的长度需要加1if (i + 1 <= n % k) len ++;res.push_back(p);//求这一段链表的结尾for (int j = 0; j < len - 1; j ++) p = p->next;if (p) {auto q = p->next;//把这一段链表的结尾赋值为空p->next = NULL;//更新 pp = q;}}return res;}
};