【力扣】725. 分隔链表

题目概述

原题链接

链表定义如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

思考过程

1. 根据题意，需要将原链表尽可能等分，设原链表长度为n，那么有三种情况
   1. n < k：即原链表长度小于要划分的组数，那么只有前面n组有元素且元素个数为1，后面k-n为空链表
   2. n = k：即原链表长度等于要划分的组数，那么刚好划分成k组且每组元素个数为1
   3. n > k：即原链表长度大于要划分的组数，那么每组划分的基数为n/k，此时还剩n%k个元素，那么只需要将多出来的n%k个元素等分给前面的链表即可
2. 以上三种情况，其实可以用统一的公式表示，即基础数量=n/k，额外链表数量=n%k，然后利用多个指针记录新的链表头即可

代码

   vector<ListNode*> splitListToParts(ListNode* root, int k) {
       int n = 0;
       ListNode* cur = root;
       // 求链表长度
       while (cur) {
           cur = cur->next;
           n++;
       }
       // 存放结果链表
       vector<ListNode*> ans;
       cur = root;
       int basic = n / k;
       ListNode* temp = cur;
       int remainder = n % k;
       for (int i = 0; i < k; i++) {
           cur = temp;
           int cnt = 1;
           int num = basic;
           // 如果不能等大小划分，那么前remainder个数量需要在基数基础上加一
           if (i < remainder) num = num + 1;
           while(cnt < num) {
               cnt++;
               // 由于此处以cnt作为循环遍历条件，所以需要对cur进行判断
               if (cur != NULL) cur = cur->next;
               else cur = NULL;
           }
           // 当cur不为空时，表明原链表后面还有元素，需要进行记录下一个链表开始，否则后面都为空
           if (cur != NULL) {
               ListNode* next = cur->next;
               cur->next = NULL;
               ans.push_back(temp);
               temp = next;
           } else {
               ans.push_back(temp);
               temp = NULL;
           }
           
       }

       return ans;
   }