LeetCode 725. 分隔链表

约 5 分钟
文章信息 7 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 需加强 1-2 华为
标签
链表

题目描述

✅ 725. 分隔链表

image-20260929062908369

image-20260929062908537

题意分析

将链表按原顺序分成恰好 k 段，k 为正整数。各段长度相差不能超过一，前面的段不能比后面的段短，返回这 k 个段头。

分隔后各段必须真正断开，不能只保存若干个仍共享后续节点的入口。如果节点数少于 k，末尾需要用空链表补足数量；空链表输入也应返回 k 个空入口。

解法：按长度切分

核心思路

[!blue]

先遍历链表得到节点总数 n。要让各段尽量平均，每段的基础长度是 base = n / k；还剩 extra = n % k 个节点，分别给 extra 个段各增加一个。这样段长只可能为 base 或 base + 1，总数又恰好等于 n。

题目要求前面的段不更短，因此把额外节点依次分给前 extra 段。第 i 段长度就是 base + (i < extra ? 1 : 0)，无需搜索切点或额外排序。

切分时，cur 始终指向下一段的第一个节点，先将它保存到结果数组。若本段长度为 size，段头已经占一个节点，只需再走 size - 1 步到达段尾，然后保存原后继、把段尾的 next 置空，再从保存的后继开始下一段。

保存后继必须先于断链，否则无法继续访问剩余节点。每次只切断两段之间的连接，段内节点顺序保持不变，各段也不再互相连接。

当 n < k，基础长度为零，前 n 段各取一个节点，剩下的目标段长为零。此时 cur 已为空，结果对应位置保持为空，断链前的判空也避免了解引用。所有分配长度总和为 n，所以既不会遗漏节点，也不会多取节点。

解题步骤

  1. 统计链表长度 n，计算 base = n / k 和 extra = n % k。
  2. 创建长度固定为 k 的结果数组，令 cur 指向原头。
  3. 对每段先保存段头，再根据段号计算目标长度。
  4. 非空段从段头再走 size - 1 步到尾部，保存下一段入口后断开连接。
  5. 继续处理下一段，空段保留空入口，最后返回完整结果数组。

代码实现

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int n = 0;

        for (ListNode cur = head; cur != null; cur = cur.next) {
            n++;
        }

        int base = n / k;
        int extra = n % k;
        ListNode[] parts = new ListNode[k];
        ListNode cur = head;

        for (int i = 0; i < k; i++) {
            parts[i] = cur;
            // 余数优先分给前面的段，保证前长后短。
            int size = base + (i < extra ? 1 : 0);

            for (int j = 1; j < size; j++) {
                cur = cur.next;
            }

            if (cur != null) {
                // 先保存下一段入口，再断开当前段。
                ListNode next = cur.next;

                cur.next = null;
                cur = next;
            }
        }

        return parts;
    }
}

func splitListToParts(head *ListNode, k int) []*ListNode {
    n := 0
    for cur := head; cur != nil; cur = cur.Next {
        n++
    }

    base, extra := n/k, n%k
    parts := make([]*ListNode, k)
    cur := head

    for i := 0; i < k; i++ {
        parts[i] = cur
        size := base
        // 余数优先分给前面的段，保证前长后短。
        if i < extra {
            size++
        }

        for j := 1; j < size; j++ {
            cur = cur.Next
        }
        if cur != nil {
            // 先保存下一段入口，再断开当前段。
            next := cur.Next
            cur.Next = nil
            cur = next
        }
    }
    return parts
}

复杂度分析

  • 时间复杂度：$O(n+k)$，统计和切分各访问链表一次，还需填充 k 个结果位置。
  • 空间复杂度：返回数组占 $O(k)$；除此之外为 $O(1)$，所有节点原地复用。

关键点总结

[!green]

  • 前长后短由余数分配决定，不需要额外排序。
  • 段头已占一个节点，到段尾只再走 size-1 步。
  • 先保存后继，再断链，最后移动当前指针。

易错点总结

[!yellow]

  • 忘记断链：返回的第一段仍会连到后续所有节点。
  • 先置空再读取后继：会丢失下一段的入口。
  • 只返回非空段：题目要求恰好 k 项，n < k 时不能缩短结果数组。
  • 空段仍解引用节点：size = 0 时当前指针可能为空，断链前必须判断。

相似题目

题目 难度 关联与区别
86. 分隔链表 中等 同样通过修改next分开链段，本题按长度连续切成k组，原题按数值稳定分成两组。
61. 旋转链表 中等 同样先得到链表长度再定位断点，原题只找旋转断点，本题按商和余数安排多个切点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/50177091
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！