47-分隔链表

自己的做法

算法思想

首先求得链表长度size。size / k = n。如果size不是k的整数倍，那么n * k 小于size。

设size - n * k = remain。即最后剩余的节点数为remain。remain一定小于n。因为要求每部分应该尽可能相等。

并且前面的要大于等于后面的长度。所以应该把最后剩余的节点均摊到前面。

即每次找到一个长度为n的链表后，按理说应该把这段链表放入结果数组中。但需要先看以下remain是否为0，如果不为0，那么将这段链表延长一个长度，即尾节点向后走一个，同时remain 减1。

并且应该添加哑节点dummy。因为最后有可能出现添加空指针的情况。

每次找到一段待添加链表后，dummy就指向下一个未添加链表的头部。所以哑节点一直指向未添加链表的头部。所以把该结点叫做pre。

算法实现

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        vector<ListNode *> res;
        int size = 0;
        ListNode * node = root;
        while (node) {
            size++;
            node = node->next;
        }
        int n = size / k;
        int remain = size - n * k;
        ListNode * pre = new ListNode();
        pre->next = root;
        node = pre;
        for(int i = 0; i < k; i++) {
            for(int j = 0; j < n; j++) {
                node = node->next;
            }
            if(remain != 0) {
                node = node->next;
                remain--;
            }
            res.push_back(pre->next);
            pre->next = node->next;
            node->next = nullptr;
            node = pre;
        }
        return res;
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：不算答案数组。只用了常数级空间。$O(1)$。算上的话，那就是$O(max(n + k))$。n为链表节点数。

参考答案类似。