AHA'S BOOK

725 分隔链表 ：给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。这 k 个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。返回一个由上述 k 部分组成的数组。

1
2
3
4
 输入：head = [1,2,3], k = 5
 输出：[[1],[2],[3],[],[]]
 输入：head = [1,2,3,4,5,6,7,8,9,10], k = 3
 输出：[[1,2,3,4],[5,6,7],[8,9,10]]

函数接口：

1
struct ListNode** splitListToParts(struct ListNode* head, int k, int* returnSize);

两趟遍历

该题就是正常的遍历，然后划分即可。首先，一次遍历计算链表的长度 size；然后，根据链表长度 size 和 k 值，计算划分的链表的长度，前 size % k 段的长度为 size / k + 1，后 size - size % k 段的长度为 size / k。

时间复杂度：O(n)，两趟遍历，空间复杂度：O(1)，不算输出占用的空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
struct ListNode** splitListToParts(struct ListNode* head, int k, int* returnSize){
    struct ListNode *node = head;
    int size = 0;

    // 计算链表长度 
    while (node) {
        size++;
        node = node->next;
    }
    node = head;

    // 申请返回的空间, 并全部初始化为 NULL
    struct ListNode **ans = (struct ListNode **)malloc(k * sizeof(struct ListNode *));
    memset(ans, 0, k * sizeof(struct ListNode *));
    
    int a = size / k, b = size % k;
    int splitSize = 0, idx = 0;
    bool save = true;
    while (node) {
        // 存储划分的每段链表的头节点 
        if (save) {
            ans[idx++] = node;
            save = false;
        }

        splitSize++;
        // 前 b 次划分的链表长度为 a+1, 后 size-b 次划分的链表长度为 a
        if (splitSize < a + (b > 0 ? 1 : 0)) {
            node = node->next;
        } else {
            splitSize = 0;
            b = fmax(--b, 0);  // b 减到 0 停止 
            save = true;
            struct ListNode *tmp = node;
            node = node->next;
            tmp->next = NULL;
        }
    }
    *returnSize = k;
    return ans;
}
aha
2023-11-01
LeetCode 链表
Expand all Back to top Go to bottom Search in blogs
银河白
豆沙绿
杏仁黄
青草绿
秋叶褐