leetcode 725.分隔連結清單（medium）

題目：n個節點，分k個部分

法1：先數對外連結表中有多少元素n，

         前n%k個部分每份n/k+1個節點，

         n%k~k部分每份有n/k個節點。

/**
 * 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) {
        //數清多少元素
        int n=0;
        ListNode* temp=root;
        while(temp!=NULL)
        {
            n++;
            temp=temp->next;
        }
        vector<ListNode*> out;
        //當輸入為空集時的情況
         if(root==NULL)
        {
            while(k--)
            {
                ListNode *s=NULL;
                out.push_back(s);
            }
            return out;
        }
        //其他情況
        ListNode *pre=NULL;
        int i=0;
        int j=1;
        while(root!=NULL)
        {
            if (j <= n%k){
		if (i == 0) out.push_back(root);
	        else if (i == n / k + 1) {i = 0; j++; pre->next=NULL; continue;}
		}
            else{
	        if (i == 0) out.push_back(root);
		else if (i == n / k) {i = 0; j++; pre->next=NULL; continue;}
	    	}
	    i++;
            pre=root;
            root = root->next;
        }
        //補空
        while(j<k)
        {
            ListNode *s=NULL;
            out.push_back(s);
            j++;
        }
        return out;
    }
};