题目描述
思路解析动画文字版
记住「先用带余除法算每段几个、再逐段切断」。前 extra 段各多拿一个,正好满足「前段不短于后段」。
先把整条链走一遍数出长度。读指针停在头节点值 1,计数 n 从 0 加到 1。
cur 沿 next 走到值 2,n 加到 2。每往后走一个节点,计数就加 1。
cur 走到值 3,n 加到 3。这一步还看不出每段分几个,得先把总长数完。
cur 走到值 4,n 加到 4。中间这几节点匀速往后,机械地数。
cur 走到值 5,n 加到 5。还没到尾,继续。
cur 走过值 5、来到值 6,n 加到 6。马上就数到尾了。
cur 走到值 7,n 加到 7。
值 7 的 next 是空,数数结束:总共 7 个节点,n = 7。有了 n 才能算每段分几个。
做带余除法:7 除以 3 商 2 余 1,所以 base = 2、extra = 1。意思是每段保底 2 个,还多出 1 个要分。
把多出来的这 1 个,分给最前面的 1 段。于是第 1 段长 base+1 = 3,第 2、3 段各长 base = 2。段长分配定下来:3、2、2,前段不短于后段。
进入第二步,按 3、2、2 逐段切。先切第 1 段,它要 3 个节点。cur 停在头节点值 1,这是第 1 段头,已走 0 步。
沿 next 走第 1 步到值 2。要到段尾需走 size−1 = 2 步,现在才走了 1 步,还差 1 步。
再走第 2 步到值 3。走满 size−1 = 2 步,值 3 就是第 1 段的尾。下一步在它和值 4 之间把 next 断开。
断开前先把值 3 的下一个节点值 4 存住做下一段头;再把值 3 的 next 设空,第 1 段 [1,2,3] 切出来了(绿色)。
切第 2 段,它要 2 个节点。cur 移到值 4,这是第 2 段头,已走 0 步,只需再走 size−1 = 1 步到段尾。
沿 next 走 1 步到值 5,走满 size−1 = 1 步,值 5 就是第 2 段的尾。下一步在值 5 和值 6 之间断开。
把值 5 的下一个值 6 存住做下一段头,再把值 5 的 next 设空:第 2 段 [4,5] 切出来了。剩下从值 6 开始。
切最后一段,它也要 2 个节点。cur 移到值 6,这是第 3 段头,已走 0 步,再走 size−1 = 1 步。
沿 next 走 1 步到值 7。值 7 正好是整条链的末尾,它就是第 3 段尾;末尾本来就没有 next,这一段不用再额外断开。
三段全部切完:[1,2,3]、[4,5]、[6,7],长度 3、2、2。回头看,数长度和切段都只走过一遍链表,这部分是 O(n);最后还要生成 k 个结果位,总体就是 O(n+k),关键全在那一步带余除法的分配上。
边界:整除则等长;n 不够则前面各 1、后面补空;k=1 整条一段。
两个高频追问:带余分配保证均匀+前段优先;n 不够时后面补空段。
参考代码
from typing import Optional, Listclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]: n = 0 cur = head while cur: n += 1 cur = cur.next base, extra = divmod(n, k) ans = [] cur = head for i in range(k): ans.append(cur) size = base + (1 if i < extra else 0) for _ in range(size - 1): if cur: cur = cur.next if cur: nxt = cur.next cur.next = None cur = nxt return ans复杂度
- 时间：O(n + k)，数长度走一遍 O(n)、切段又走一遍 O(n),再加上要返回 k 个头,合起来 O(n + k)
- 空间：O(k)，除返回的 k 个头数组外只用了几个指针,额外空间 O(1);算上返回数组是 O(k)
易错点
面试追问把动画讲成自己的话
追问怎么保证各段长度差不超过 1、且前段不短于后段?
追问链表比段数还短(n < k)怎么办?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
链表组件
LeetCode 817 · 中等 · 沿着 链表套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题