Medium

题目描述

给定一个单链表的头节点 head 和一个整数 k，将链表分割成 k 个连续的部分。

每部分的长度应该尽可能相等：任意两部分的大小差不应该超过 1。这可能会导致有些部分为 null。

这些部分应该按照在输入链表中出现的顺序进行排列，并且排在前面的部分的大小应该大于或等于排在后面的部分的大小。

返回由 k 个部分组成的数组。

示例 1：

输入：head = [1,2,3], k = 5
输出：[[1],[2],[3],[],[]]
解释：
第一个元素 output[0] 的值为 output[0].val = 1，output[0].next = null。
最后一个元素 output[4] 为 null，但它作为 ListNode 的字符串表示是 []。

示例 2：

输入：head = [1,2,3,4,5,6,7,8,9,10], k = 3
输出：[[1,2,3,4],[5,6,7],[8,9,10]]
解释：
输入被分成了几个连续的部分，并且每部分的长度相差不超过 1。前面部分的长度大于等于后面部分的长度。

约束条件：

  • 链表中节点的数量在 [0, 1000] 范围内
  • 0 <= Node.val <= 1000
  • 1 <= k <= 50

解题思路

解题思路

这道题的关键在于理解如何均匀分配链表节点。我们需要将 n 个节点分配到 k 个部分中，使得每部分长度尽可能相等。

核心分配规律：

  • 如果链表有 n 个节点，分成 k 部分
  • 每部分基础长度为 n // k
  • 前 n % k 个部分需要额外分配一个节点

算法步骤：

  1. 首先遍历链表计算总长度 n
  2. 计算每部分的基础长度 part_size = n // k
  3. 计算需要额外节点的部分数量 extra = n % k
  4. 依次分割链表：
    • 前 extra 个部分长度为 part_size + 1
    • 其余部分长度为 part_size
    • 分割时要断开链表连接

实现要点：

  • 使用双指针技巧，一个指向当前部分头节点，一个用于遍历
  • 每次分割完一部分后，要将该部分的尾节点的 next 指针置为 null
  • 如果某部分长度为 0，则该部分为 null

时间复杂度为 O(n)，空间复杂度为 O(1)（不考虑结果数组）。

代码实现

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        // 计算链表长度
        int n = 0;
        ListNode* curr = head;
        while (curr) {
            n++;
            curr = curr->next;
        }
        
        // 计算每部分的长度
        int part_size = n / k;
        int extra = n % k;
        
        vector<ListNode*> result(k);
        curr = head;
        
        for (int i = 0; i < k; i++) {
            result[i] = curr;
            
            // 当前部分的长度
            int current_size = part_size + (i < extra ? 1 : 0);
            
            // 如果当前部分长度为0，则为null
            if (current_size == 0) {
                result[i] = nullptr;
                continue;
            }
            
            // 移动到当前部分的最后一个节点
            for (int j = 0; j < current_size - 1; j++) {
                curr = curr->next;
            }
            
            // 断开连接
            ListNode* next = curr->next;
            curr->next = nullptr;
            curr = next;
        }
        
        return result;
    }
};

class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
        # 计算链表长度
        n = 0
        curr = head
        while curr:
            n += 1
            curr = curr.next
        
        # 计算每部分的长度
        part_size = n // k
        extra = n % k
        
        result = []
        curr = head
        
        for i in range(k):
            result.append(curr)
            
            # 当前部分的长度
            current_size = part_size + (1 if i < extra else 0)
            
            # 如果当前部分长度为0，则为None
            if current_size == 0:
                result[i] = None
                continue
            
            # 移动到当前部分的最后一个节点
            for j in range(current_size - 1):
                curr = curr.next
            
            # 断开连接
            next_node = curr.next
            curr.next = None
            curr = next_node
        
        return result

public class Solution {
    public ListNode[] SplitListToParts(ListNode head, int k) {
        // 计算链表长度
        int n = 0;
        ListNode curr = head;
        while (curr != null) {
            n++;
            curr = curr.next;
        }
        
        // 计算每部分的长度
        int partSize = n / k;
        int extra = n % k;
        
        ListNode[] result = new ListNode[k];
        curr = head;
        
        for (int i = 0; i < k; i++) {
            result[i] = curr;
            
            // 当前部分的长度
            int currentSize = partSize + (i < extra ? 1 : 0);
            
            // 如果当前部分长度为0，则为null
            if (currentSize == 0) {
                result[i] = null;
                continue;
            }
            
            // 移动到当前部分的最后一个节点
            for (int j = 0; j < currentSize - 1; j++) {
                curr = curr.next;
            }
            
            // 断开连接
            ListNode next = curr.next;
            curr.next = null;
            curr = next;
        }
        
        return result;
    }
}

var splitListToParts = function(head, k) {
    let length = 0;
    let curr = head;
    while (curr) {
        length++;
        curr = curr.next;
    }
    
    let partSize = Math.floor(length / k);
    let extraNodes = length % k;
    
    let result = [];
    curr = head;
    
    for (let i = 0; i < k; i++) {
        let partHead = curr;
        let currentPartSize = partSize + (i < extraNodes ? 1 : 0);
        
        for (let j = 0; j < currentPartSize - 1 && curr; j++) {
            curr = curr.next;
        }
        
        if (curr) {
            let next = curr.next;
            curr.next = null;
            curr = next;
        }
        
        result.push(partHead);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历链表两次：一次计算长度，一次进行分割
空间复杂度O(1)除了结果数组外，只使用了常数个额外变量

相关题目