725-分块链表

LeetCode 725. Split Linked List in Parts

LeetCode-725

Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list "parts".

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Example 1:

Input: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

method

mod余数要分配到前面的num每一个，也就是前面的每个num都要加1，直到余数减到0

注意：k会比链表长度大，多的就是空

vector<ListNode*> splitListToParts(ListNode* root, int k) {
    int len = 0;    // 求链表长度
    ListNode *cur = head;
    while (cur) {
        len++;
        cur = cur->next;
    }
    int num = len / k;  // 每块有多少个
    int mod = len % k;  // 还剩多少个，要均匀分配
    vector<ListNode*> res(k);   // k会比len大，所以只能这样初始化
    for (int i = 0; head && i < k; ++i) {  // k会比len大，但是head没有了就可以退出了
        res[i] = head;
        int count = mod-- > 0 ? num + 1 : num;    // 有余数就加1
        while (--count) head = head->next;// 从第一个节点开始走，走count-1步
        ListNode *tmp = head->next;
        head->next = nullptr;   // 断开之后块就分出来了
        head = tmp;
    }
    return res;
}