NeetCode #337LC-725MediumLinked List
← Back to All Problems#337 · #725 · Split Linked List in Parts(分隔链表)
📌 Problem Statement & Constraints
Given the head of a singly linked list and an integer
k, split the list into k consecutive parts. The parts must have sizes differing by at most 1, with the earlier parts being the larger ones. Return an array of the k heads (using null for empty parts). Constraints: 1 <= k <= 50, 0 <= number of nodes <= 1000.💡 Core Algorithmic Approaches
- Compute the length
n, thensize, rem = divmod(n, k). The firstremparts havesize + 1nodes and the rest havesize. - Walk the list, cutting off each part by setting its tail's
nexttoNone. - When
size == 0andrem == 0, the part is empty andNoneis appended. - Each node is visited once, so the whole thing is O(n + k).
💻 Benchmark Python3 Implementation
class Solution:
def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
n = 0
cur = head
while cur:
n += 1
cur = cur.next
size, rem = divmod(n, k) # rem parts get one extra node
res = []
cur = head
for i in range(k):
part_size = size + (1 if i < rem else 0)
if part_size == 0:
res.append(None) # empty part
continue
part_head = cur
for _ in range(part_size - 1): # walk to the part's tail
cur = cur.next
nxt = cur.next
cur.next = None # cut the part off
res.append(part_head)
cur = nxt
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + k): one pass for the length, one pass to cut the parts.
💾 Space Complexity
O(k) for the result array.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting to cut with
cur.next = None: the parts would all be linked together. - Distributing the remainder to the last parts: the earlier parts must be the larger ones.
- Walking
part_sizesteps instead ofpart_size - 1:curstarts at the part's head, so onlypart_size - 1steps reach the tail. - Handling
n < k: some parts are empty, hence theNoneentries.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Linked List Problems
中文速览与面试要点
分隔链表
给你一个头结点为 head 的单链表和一个整数 k,请你设计一个算法将链表分隔为 k 个连续的部分。每部分的长度应该尽可能的相等:任意两部分的长度差距不能超过 1。这可能会导致有些部分为 null。这 k 个部分应该按照在链表中出现的顺序排列,并且排在前面的部分的长度应该 大于或等于 排在后面的部分的长度。返回一个由上述 k 部分组成的数组。约束:链表中节点的数目在范围 [0, 1000] 内;0 ≤ Node.val ≤ 1000;1 ≤ k ≤ 50。
核心要点
- 先求长度再按余数分配(标准解) :① 遍历求总长度 n;② base, extra = divmod(n, k) ,前 extra 个部分长度为 base + 1 ,其余为 base ;③ 逐段切开。
- 为什么前 extra 段多一个 :题目要求「排在前面的部分的长度大于或等于后面的」,因此把余数分给前 extra 段。
- 切段的实现 :记录每段的头节点,走 size − 1 步到达该段尾节点,先暂存 cur.next (下一段的头),再把 cur.next = None 断开。
- 长度为 0 的部分 :直接向结果数组中放 None,无需操作链表。
常见陷阱
- 不先求长度而按 n // k 估算 :无法正确处理余数分配。必须先求 n 再用 divmod。
- 把余数分给后面的段 :题目要求前面的段更长,因此余数应分给 前 extra 段 。
- 忘记 cur.next = None 断开 :会让每段的尾节点仍指向下一段,返回的数组中的各段并非独立链表。
- size == 0 时仍执行 cur = cur.next : cur 已为 None,会抛 AttributeError。必须 continue 。
- 忘记暂存 nxt : cur.next = None 会丢失下一段的头。
参考实现
class Solution:
def splitListToParts(self, head: 'ListNode', k: int) -> list:
# ① 求总长度
n = 0
cur = head
while cur:
n += 1
cur = cur.next
base, extra = divmod(n, k) # 前 extra 段长度为 base+1
res = []
cur = head
for i in range(k):
size = base + (1 if i < extra else 0)
if size == 0:
res.append(None) # 该段为空
continue
res.append(cur) # 该段的头节点
for _ in range(size - 1): # 走到该段尾节点
cur = cur.next
nxt = cur.next # 暂存下一段的头
cur.next = None # 断开
cur = nxt
return res