⚡Flashcard Drill➔
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

  1. Compute the length n, then size, rem = divmod(n, k). The first rem parts have size + 1 nodes and the rest have size.
  2. Walk the list, cutting off each part by setting its tail's next to None.
  3. When size == 0 and rem == 0, the part is empty and None is appended.
  4. 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_size steps instead of part_size - 1: cur starts at the part's head, so only part_size - 1 steps reach the tail.
  • Handling n < k: some parts are empty, hence the None entries.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems