LeetCode 725. 分隔链表

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

题目描述

✅ 725. 分隔链表

image-20250416224455601

image-20250416224519644

题意分析

要把一条单链表切成恰好 k 段，返回一个长度固定为 k 的数组。三条硬约束必须同时满足：任意两段长度之差不超过 1；靠前的段不能比靠后的段短；原链表的相对顺序不能变。最后一条意味着不允许重新组织节点，只能沿着链表从头到尾一刀一刀切下去。

「返回长度为 k 的数组」这句话透露了一个容易被忽略的信号：当链表长度 n 小于 k 时，后面的若干段必须是空链表，而不是把数组缩短。所以结果数组的长度由 k 决定，与 n 无关。

「长度差不超过 1」加上「前面的不短于后面的」这两条合起来，其实已经把每段长度唯一确定了，没有任何自由度。这提示不需要搜索或贪心，只要先把每段该有多长算清楚，剩下的就是纯粹的指针搬运。

边界上要考虑：head 为空（所有段都是空）；n 小于 k（前 n 段各 1 个节点，后 k - n 段为空）；n 恰好被 k 整除（每段等长，没有多余节点）；k 等于 1（整条链表原样返回）。

另外注意「切」是物理切断，不是逻辑标记——每段的尾节点 next 必须置空，否则返回的每一段都会一路串到链表末尾。

解法：按长度切分

核心思路

每段长度取决于链表总长度，因此先遍历一次得到 n。设 base = n / k、extra = n % k，则前 extra 段长度为 base + 1，其余段长度为 base。这样所有段长度只可能相差 1，而且较长段都在前面。

第二遍沿原链表切分，不复制节点。处理第 i 段前维护不变量：前 i 段已经按目标长度断开，cur 指向第一个尚未分配的节点。记录 cur 为本段头，前进到本段尾；先保存尾节点的 next，再把 next 置空，最后从保存的位置继续。

当 n < k 时，base = 0、extra = n，前 n 段各取一个节点，后面自动得到 null，无需另写分支。

正确性说明：各段长度之和为 extra × (base + 1) + (k - extra) × base = n，所以每个节点恰好分配一次；段长仅为 base 或 base + 1，且较长段在前，满足题目两项长度约束。每次只在段尾断开，不改变节点相对次序。循环结束后得到恰好 k 段，结果正确。

解题步骤

  • 遍历链表，统计节点数 n。
  • 计算 base = n / k、extra = n % k，并创建长度为 k 的结果数组。
  • 对第 i 段，令 size = base + 1（i < extra）或 base。
  • 保存段头，从段头再走 size - 1 步到段尾；先保存下一段头，再断开当前段。
  • 重复 k 次并返回结果。

例如 n = 10, k = 3 时，base = 3, extra = 1，段长为 [4,3,3]。n = 3, k = 5 时段长为 [1,1,1,0,0]，结果后两项为 null。空链表则返回 k 个 null。

代码实现

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)。统计长度访问 n 个节点；切分阶段总共再访问 n 个节点，并写入 k 个结果位置。
  • 空间复杂度：O(1)（不计返回数组）。结果数组占 O(k)，除此之外只使用固定数量的变量，所有节点原地复用。

关键点总结

  • “均分且前长后短”可直接转化为 base = n / k、extra = n % k。
  • 第 i 段长度统一写成 base + (i < extra ? 1 : 0)，避免为 n < k 单独设计流程。
  • 指针操作遵守“先保存后继，再断链”，否则会丢失下一段入口。
  • 结果长度固定为 k；空段必须以 null/nil 保留。

易错点总结

  • 前进 size 步再断链：[1,2,3,4,5,6], k = 2 会把第一段切成 4 个节点。段头已经占一个位置，只需再走 size - 1 步。
  • 忘记断开段尾：[1,2,3,4], k = 2 返回的第一段会继续连到 4，看起来仍是整条链表。
  • 先执行 cur.next = null 再读取 cur.next：下一段入口立即丢失，后续结果全为 null。必须先保存 next。
  • 把余数分给后面的段：n = 7, k = 3 会得到长度 [2,2,3]，违反前面的段不能更短；正确长度是 [3,2,2]。
  • 结果数组只开 min(n, k) 个位置：n = 3, k = 5 时会少两个空段，不满足“恰好 k 段”。
  • 未处理 size = 0 就解引用 cur：空链表或 n < k 的尾部空段会触发空指针异常；断链前必须判断 cur != null。

相似题目

题目 难度 考察点
86. 分隔链表 中等 按值域而非长度划分，需要两条哑结点链表分别串联后拼接，不涉及长度计算
61. 旋转链表 中等 同样先统计长度再取模，但要先成环再在指定位置断开，切点由 k 取模决定
143. 重排链表 中等 找中点后反转后半段再交替归并，切分只是第一步，重点在反转与合并
328. 奇偶链表 中等 按下标奇偶拆成两条链再首尾相接，需要同时推进两个游标而非单游标
19. 删除链表的倒数第 N 个结点 中等 用快慢指针一趟定位，避免了先统计长度的第一遍遍历，考察双指针间距