⚡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

中文速览与面试要点

分隔链表

给你一个头结点为 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