用出++编程,并包含main函数:给你一个头结点为 head 的单链表和一个整数 k ,请你设计一个算法将链表分隔为 k 个连续的部分。 每部分的长度应该尽可能的相等:任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。 这 k 个部分应该按照在链表中出现的顺序排列,并且排在前面的部分的长度应该大于或等于排在后面的长度。 返回一个由上述 k 部分组成的数组。并逐句解释代码
时间: 2024-02-23 11:57:53 浏览: 66
当然,我会尽力回答你的问题。下面是满足你要求的代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 链表节点的定义
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
vector<ListNode*> splitListToParts(ListNode* head, int k) {
// 先计算链表的长度
int len = 0;
ListNode *cur = head;
while (cur != NULL) {
len++;
cur = cur->next;
}
// 计算每个部分的长度
int partSize = len / k; // 每个部分的基本长度
int remainder = len % k; // 长度余数,用于平均分配到每个部分
vector<ListNode*> res; // 存储结果的数组
cur = head; // 当前节点指针
for (int i = 0; i < k; i++) {
res.push_back(cur); // 将当前节点作为当前部分的头节点
int curSize = partSize + (remainder-- > 0 ? 1 : 0); // 计算当前部分的长度
if (cur != NULL) {
for (int j = 1; j < curSize; j++) {
cur = cur->next; // 将当前节点后移,直到当前部分的最后一个节点
}
ListNode *next = cur->next; // 记录当前节点的下一个节点
cur->next = NULL; // 将当前节点的 next 指针置空,断开链表
cur = next; // 将当前节点后移一位,准备处理下一部分
}
}
return res;
}
// 测试代码
int main() {
ListNode *head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
int k = 3;
vector<ListNode*> res = splitListToParts(head, k);
for (int i = 0; i < res.size(); i++) {
ListNode *cur = res[i];
while (cur != NULL) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
return 0;
}
```
这段代码可以将一个单链表分隔为 k 个连续的部分,并返回一个由这些部分组成的数组。我们来逐句解释一下代码:
```cpp
vector<ListNode*> splitListToParts(ListNode* head, int k) {
// 先计算链表的长度
int len = 0;
ListNode *cur = head;
while (cur != NULL) {
len++;
cur = cur->next;
}
// 计算每个部分的长度
int partSize = len / k; // 每个部分的基本长度
int remainder = len % k; // 长度余数,用于平均分配到每个部分
vector<ListNode*> res; // 存储结果的数组
cur = head; // 当前节点指针
for (int i = 0; i < k; i++) {
res.push_back(cur); // 将当前节点作为当前部分的头节点
int curSize = partSize + (remainder-- > 0 ? 1 : 0); // 计算当前部分的长度
if (cur != NULL) {
for (int j = 1; j < curSize; j++) {
cur = cur->next; // 将当前节点后移,直到当前部分的最后一个节点
}
ListNode *next = cur->next; // 记录当前节点的下一个节点
cur->next = NULL; // 将当前节点的 next 指针置空,断开链表
cur = next; // 将当前节点后移一位,准备处理下一部分
}
}
return res;
}
```
首先,我们定义了一个函数 `splitListToParts`,该函数接受一个单链表的头节点 `head` 和一个整数 `k`,返回一个由 `k` 个部分组成的数组,每个部分是一个单链表。
接下来,我们用一个变量 `len` 记录链表的长度,用一个指针 `cur` 遍历整个链表,计算出链表的长度。
然后,我们计算每个部分的长度。我们先计算出每个部分的基本长度 `partSize`,即链表长度除以 `k` 的商。如果链表长度不能被 `k` 整除,就需要将余数平均分配到前面的部分中,因此我们用 `remainder` 变量记录余数,并在计算每个部分的长度时,如果余数大于 0,就将当前部分的长度加 1。
接下来,我们创建一个 `vector` 类型的变量 `res`,用于存储最终的结果。我们将当前节点指针 `cur` 初始化为头节点 `head`,然后开始循环,共循环 `k` 次,处理每个部分。
在循环中,我们先将当前节点 `cur` 添加到结果数组 `res` 中,作为当前部分的头节点。然后计算出当前部分的长度 `curSize`,根据上面的计算方法,如果余数大于 0,就将当前部分的长度加 1。
接下来,我们需要将当前节点 `cur` 后移,直到当前部分的最后一个节点。我们用一个循环将当前节点后移 `curSize-1` 次,即可找到当前部分的最后一个节点。在这个过程中,需要注意判断当前节点是否为 NULL,防止出现空指针异常。
当我们找到当前部分的最后一个节点后,我们需要将当前链表断开,将当前节点的 `next` 指针置空,这样就可以将当前部分从原链表中分离出来。然后我们将当前节点 `cur` 后移一位,准备处理下一部分。
最后,我们返回结果数组 `res`,即可得到分隔后的链表。我们在 `main` 函数中测试了一下代码的正确性。
阅读全文