725分隔链表成几个部分

725.分割链表

注：现在开始尽量减少以图片的方式呈现题目了

以下是题目

/*
给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。

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

返回一个符合上述规则的链表的列表。

举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

示例 1：

输入: 
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表，而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。
示例 2：

输入: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释:
输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。
 

提示:

root 的长度范围： [0, 1000].
输入的每个节点的大小范围：[0, 999].
k 的取值范围： [1, 50].
*/

以下是题目给出的代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* root, int k) {

    }
};

很显然，题目的难点就是怎么设置每个存储链表单位的长短，因为他说每部分的长度相差不超过1，每部分的长度大于等于后面部分的长度

/*
	长度为10，分组为2，那么每个单位存储两个节点，共5个单位
	长度为10，分组为3，那么 4 3 3
	长度为10，分组为4，那么3 3 3 2
	
	于是我想用数组来存储，首先均分，然后再把余数均匀分摊到前几项
	我的思考，就是
	1.先用所有数/组 得到 基
	2.再用数%组 得到余数
	3.在前几项的基上+1，一直到余数被分光
	4.把这些项存到一个数组中
	
	然后就是断开链表，把头节点放入链表数组中去
	
	注意，这里有有几个细节
	1.如果这个组为1长度，直接插入头节点
	2.如果这个组为0长度，插入NULL
	
	代码量会长一点，因为能让自己看懂
*/

class Solution {
public:
  vector<ListNode*> splitListToParts(ListNode* root, int k) {
    
        vector<ListNode *> parts;
        vector<int> install;
        ListNode *cur = root,*temphead = root;
      //这一部分，就是计算链表中节点的个数
        int number = 0;
        while (cur) {
            cur = cur->next;
            number++;
        }
        cur = root;
        //这里分两类，当组数大于长度，那么前面几组为1长度，后面为0长度
        int cnt = 0;
        if(k>number)
        {
            while(cnt<number)
            {
                install.push_back(1);
                cnt++;
            }
            while(cnt<k)
            {
                install.push_back(0);
                cnt++;
            }
        } else
        {   
            int integer = number / k;
            int remainder = number % k;
            while (remainder) {
                install.push_back(integer + 1);
                remainder--;
                cnt++;
            }
            while(cnt<k)
            {
                install.push_back(integer);
                cnt++;
            }
            
        }
      
      //下面是切割操作，如果组数大于长度，那么如果单位长度为1.返回头节点，同时做头结点的更新，否则在数组中插入NULL节点
        if(k>number)
        {
            for(int i = 0;i<install.size();i++)
            {
                int tempCnt = 0;

                if(install[i]==0)
                    parts.push_back(NULL);
                else
                {
                    temphead = cur->next;
                    cur->next = NULL;
                    parts.push_back(cur);
                    cur = temphead;  
                }
                     
            }
        }else
//	   否则，按照每个单位长度来切割链表，我这里用了三个节点，一个节点用来记录头节点，一个用来记录尾节点，还有一个临时节点用来帮助头节点和尾节点完成更新
           
        {
            for(int i = 0;i<install.size();i++)
            {
                int tempCnt = 0;
                while(tempCnt<install[i]-1)
                {
                    tempCnt++;
                    cur = cur->next;
                }
                ListNode *next = cur->next;
                cur->next = NULL;
                parts.push_back(temphead);
                cur = next;
                temphead=next;
            }
        }
       
    return parts;

    }
};