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.