分隔链表 图解题解

这道题到底在问什么

输入

head=[1,2,3,4,5,6,7], k=3

输出

[[1,2,3],[4,5],[6,7]]

输入

head=[1,2,3], k=5

输出

[[1],[2],[3],[],[]]

最优解：一步一步想明白

1. 3记住「先用带余除法算每段几个、再逐段切断」。前 extra 段各多拿一个,正好满足「前段不短于后段」。
2. 4先把整条链走一遍数出长度。读指针停在头节点值 1,计数 n 从 0 加到 1。
3. 5cur 沿 next 走到值 2,n 加到 2。每往后走一个节点,计数就加 1。
4. 6cur 走到值 3,n 加到 3。这一步还看不出每段分几个,得先把总长数完。
5. 7cur 走到值 4,n 加到 4。中间这几节点匀速往后,机械地数。
6. 8cur 走到值 5,n 加到 5。还没到尾,继续。
7. 9cur 走过值 5、来到值 6,n 加到 6。马上就数到尾了。
8. 10cur 走到值 7,n 加到 7。
9. 11值 7 的 next 是空,数数结束:总共 7 个节点,n = 7。有了 n 才能算每段分几个。
10. 12做带余除法:7 除以 3 商 2 余 1,所以 base = 2、extra = 1。意思是每段保底 2 个,还多出 1 个要分。
11. 13把多出来的这 1 个,分给最前面的 1 段。于是第 1 段长 base+1 = 3,第 2、3 段各长 base = 2。段长分配定下来:3、2、2,前段不短于后段。
12. 14进入第二步,按 3、2、2 逐段切。先切第 1 段,它要 3 个节点。cur 停在头节点值 1,这是第 1 段头,已走 0 步。
13. 15沿 next 走第 1 步到值 2。要到段尾需走 size−1 = 2 步,现在才走了 1 步,还差 1 步。
14. 16再走第 2 步到值 3。走满 size−1 = 2 步,值 3 就是第 1 段的尾。下一步在它和值 4 之间把 next 断开。
15. 17断开前先把值 3 的下一个节点值 4 存住做下一段头;再把值 3 的 next 设空,第 1 段 [1,2,3] 切出来了(绿色)。
16. 18切第 2 段,它要 2 个节点。cur 移到值 4,这是第 2 段头,已走 0 步,只需再走 size−1 = 1 步到段尾。
17. 19沿 next 走 1 步到值 5,走满 size−1 = 1 步,值 5 就是第 2 段的尾。下一步在值 5 和值 6 之间断开。
18. 20把值 5 的下一个值 6 存住做下一段头,再把值 5 的 next 设空:第 2 段 [4,5] 切出来了。剩下从值 6 开始。
19. 21切最后一段,它也要 2 个节点。cur 移到值 6,这是第 3 段头,已走 0 步,再走 size−1 = 1 步。
20. 22沿 next 走 1 步到值 7。值 7 正好是整条链的末尾,它就是第 3 段尾;末尾本来就没有 next,这一段不用再额外断开。
21. 23三段全部切完:[1,2,3]、[4,5]、[6,7],长度 3、2、2。回头看,数长度和切段都只走过一遍链表,这部分是 O(n);最后还要生成 k 个结果位,总体就是 O(n+k),关键全在那一步带余除法的分配上。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import Optional, List
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class 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

#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        int n = 0;
        for (auto p = head; p; p = p->next) n++;
        int base = n / k, extra = n % k;
        vector<ListNode*> ans;
        ListNode* cur = head;
        for (int i = 0; i < k; ++i) {
            ans.push_back(cur);
            int size = base + (i < extra);
            for (int j = 1; j < size && cur; ++j) cur = cur->next;
            if (cur) { ListNode* nxt = cur->next; cur->next = nullptr; cur = nxt; }
        }
        return ans;
    }
};

import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int n = 0;
        for (ListNode p = head; p != null; p = p.next) n++;
        int base = n / k, extra = n % k;
        ListNode[] ans = new ListNode[k];
        ListNode cur = head;
        for (int i = 0; i < k; i++) {
            ans[i] = cur;
            int size = base + (i < extra ? 1 : 0);
            for (int j = 1; j < size && cur != null; j++) cur = cur.next;
            if (cur != null) {
                ListNode next = cur.next;
                cur.next = null;
                cur = next;
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问