leetcode  725. 分隔链表 meidum

题目描述：

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 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:vector<ListNode*> splitListToParts(ListNode* head, int k) {if (k <=0 )return {};// 遍历链表得到其长度int n = 0;ListNode* cur = head;while(cur) {n++;cur = cur->next;}int avg = n / k; // 每个子链表平均元素的个数int mod = n % k; // 余数cur = head;vector<ListNode*> res(k, nullptr);for (int i = 0; i < k && cur; i++){res[i] = cur;int one_len = avg;if (mod){mod--;one_len++;}// 移动到当前这一段最后一个for (int j = 0; j < one_len - 1; j++)cur = cur->next;ListNode* tmp = cur->next;cur->next = nullptr;cur = tmp;}return res;}
};

---