Leetcode 725. Split Linked List in Parts

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

Split Linked List in Parts

2. Solution

/**
 * 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) {
        vector<ListNode*> result;
        int n = 0;
        ListNode* current = root;
        while(current && current->next) {
            current = current->next->next;
            n += 2;
        }
        if(current) {
            n += 1;
        }
        int partitions = 0;
        int remainder = 0;
        if(k >= n) {
            partitions = 1;
        }
        else {
            partitions = n / k;
            remainder = n % k;
        }
        ListNode* pre = nullptr;
        current = root;
        while(remainder) {
            int count = partitions + 1;
            result.push_back(current);
            while(count) {
                count--;
                pre = current;
                current = current->next;
            }
            pre->next = nullptr;
            remainder--;
        }
        while(current) {
            int count = partitions;
            result.push_back(current);
            while(count) {
                count--;
                pre = current;
                current = current->next;
            }
            pre->next = nullptr;
        }
        while(result.size() < k) {
            result.push_back(nullptr);
        }
        return result;
    }
};

Reference

1. https://leetcode.com/problems/split-linked-list-in-parts/description/