▶ 将一个单链表拆分为长度尽量接近的 k 段
● 自己的代码，12 ms
■ 记链表长度为 count，目标段数为 k，quo = count / k，mod = count % k，part = mod * (quo + 1)
■ 前半截（长半截）共有 mod 组，每组 quo + 1 个元素，共 mod * (quo + 1) 个元素，这是 part 的由来；后半截（长半截）共有 k - mod 组，每组 quo 个元素，共 quo * (k - mod) 个元素
■ 当 i < part 时，第 i 元素处于前半截，组号 s = i / (quo + 1)，该组最后一个元素下标为 t = (quo + 1) * (s + 1) - 1，即满足 (t + 1) % (quo + 1) == 0
■ 当 i >= part 时，第 i 元素处于后半截，组号 s = （i - part） / quo + mod = (i - mod) / quo，该组最后一个元素下标为 t = (s + 1) * quo + mod - 1 （前面所有组的元素个数，注意偏移量 mod），即满足 (t + 1 - mod) % quo == 0
class Solution
{
public:
vector<ListNode*> splitListToParts(ListNode* root, int k)
{
vector<ListNode *> table(k, nullptr);
if (root == nullptr)
return table;
int count, i;
ListNode *p, *q;
for (p = root, count = ; p->next != nullptr; p = p->next, count++);// 计算结点数
const int quo = count / k, mod = count % k, mod * (quo + );
for (p = table[] = root, i = ; p != nullptr && p->next != nullptr; i++)
{
if (i < part && !((i + ) % (quo + )))// p 指向了前半截某组的末尾结点
{
q = p->next, p->next = nullptr, p = q;
table[(i + ) / (quo + )] = q; // 注意此时是在table 中挂上 q 指向的结点，相当于第 i + 1 个结点
}
else if (i >= part && !((i + - mod) % quo))// p 指向了后半截某组的末尾结点
{
q = p->next, p->next = nullptr, p = q;
table[(i + - mod) / quo] = q;
}
else
p = p->next;
}
return table;
}
};
● 大佬的代码，11 ms，使用简单的判断 idx < remainder 来确认切分位置
class Solution
{
public:
vector<ListNode*> splitListToParts(ListNode* root, int k)
{
if (k == )
return vector<ListNode*>{ root };
vector<ListNode*> res(k, nullptr);
ListNode *temp;
int len, idx, tmp;
for (len = , temp = root; temp != nullptr; len++, temp = temp->next);
const int per_len = len / k, remainder = len % k; for (idx = ; idx < k; )
{
tmp = per_len + (idx < remainder ? : );
if (tmp == )
{
res[idx++] = nullptr;
continue;
}
for (res[idx++] = root; tmp != ; root = root->next, tmp--);
temp = root->next, root->next = nullptr, root = temp;
} return res;
}
};
● 大佬的方法，11 ms，号称不需要知道链表的长度。每次指针 slow 移动一格，指针 fast 移动 k 格，直到 fast 抵达链表尾部，这时 slow 大约移动了 n / k 格，即为分界点。实际上 fast 在整个过程中移动了 O(n) 的次数，还不如提前一趟遍历计算链表的长度
class Solution
{
public :
vector<ListNode *> splitListToParts(ListNode *root, int k)
{
vector<ListNode *> res(k, nullptr);
ListNode *fast, *slow;
int i, step;
for (i = ; i < k; i++)
{
if (root == nullptr)
break;
for (slow = root, fast = root, step = k;;)
{
fast = move(fast, step);
if (fast != nullptr)
slow = slow->next;
else
break;
}
res[i] = root;
if (slow->next != nullptr)
{
root = slow->next;
slow->next = nullptr;
}
else
break;
step--;
}
return res;
}
ListNode* move(ListNode *node, int step)
{
for(;step > ;)
{
node = node->next;
step--;
if (node == nullptr)
break;
}
return node;
}
};