(链表专题) 725. 分隔链表 ——【Leetcode每日一题】

我不是女神ヾ 2024-03-24 17:44 66阅读 0赞

### 725. 分隔链表 ###

给你一个头结点为 `head` 的单链表和一个整数 `k` ，请你设计一个算法将链表分隔为 `k` 个连续的部分。

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

这 `k` 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 `k` 部分组成的数组。

##### 示例 1： #####

![在这里插入图片描述][b121c60f88964ea8a8235850faca2745.png]

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

##### 示例 2： #####

![在这里插入图片描述][f0fb9769f70143f6a8c4db57e5cbf57e.png]

> **输入**：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

#### 思路：（数学常识） ####

*  首先要知道链表的长度，即链表中一共有多少个结点 `num`；
 *  然后根据要分隔成`k`个部分，计算每个部分最少分多少个`len`；
 *  然后把多余的分给前`mod`个部分，每个部分分一个。

#### 代码：(Java、C++) ####

**Java**

/**
     * Definition for singly-linked list.
     * public 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 num = 0;
            ListNode tem = head;
            while(tem != null){
        
                num++;
                tem = tem.next;
            }
            int len = num / k;
            int mod = num % k;
            ListNode[] ans = new ListNode[k];
            ListNode h = head;//保存分割后的头节点
            for(int i = 1; i <= num; i++){
        
                if(mod > 0 && i % (len + 1) == 0){
        
                    tem = head.next;
                    head.next = null;
                    ans[(i - 1) / (len + 1)] = h;
                    head = tem;
                    h = head;
                    mod--;
                }else if(mod < 1 && (i - num % k) % len == 0){
        
                    tem = head.next;
                    head.next = null;
                    ans[(i - num % k - 1) / len] = h;
                    head = tem;
                    h = head;
                }else{
        
                    head = head.next;
                }
            }
            return ans;
        }
    }

**C++**

/**
     * Definition for singly-linked list.
     * 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 num = 0;
            ListNode* tem = head;
            while(tem != NULL){
        
                num++;
                tem = tem->next;
            }
            int len = num / k;
            int mod = num % k;
            vector<ListNode*> ans;
            ListNode* h = head;//保存分割后的头节点
            for(int i = 1; i <= num; i++){
        
                if(mod > 0 && i % (len + 1) == 0){
        
                    tem = head->next;
                    head->next = NULL;
                    ans.push_back(h);
                    head = tem;
                    h = head;
                    mod--;
                }else if(mod < 1 && (i - num % k) % len == 0){
        
                    tem = head->next;
                    head->next = NULL;
                    ans.push_back(h);
                    head = tem;
                    h = head;
                }else{
        
                    head = head->next;
                }
            }
            while(ans.size() < k){
        
                ans.push_back(NULL);
            }
            return ans;
        }
    };

##### 运行结果： #####

![在这里插入图片描述][52e60fe963294b7daca1c22a94019b67.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，其中 `n` 是链表的长度。需要遍历链表两次，得到链表的长度和分隔链表。
 *  **空间复杂度**： O ( 1 ) O(1) O(1)。只使用了常量的额外空间，注意返回值不计入空间复杂度。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[b121c60f88964ea8a8235850faca2745.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3f00cacebebc4d6db8613b68f818b244.png
[f0fb9769f70143f6a8c4db57e5cbf57e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/626cfd9cf273425e859b7f2ec6ed3e5c.png
[52e60fe963294b7daca1c22a94019b67.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/0ec4e533f7864394802dfce27fd40384.png
[Link 1]: https://leetcode.cn/problems/split-linked-list-in-parts/description/?orderBy=most_votes
[leetCode]: http://t.csdn.cn/kQLJO