leetcode 725. Split Linked List in Parts | 725. 分隔链表（Java）

淩亂°似流年 2022-09-14 02:27 143阅读 0赞

## 题目 ##

[https://leetcode.com/problems/split-linked-list-in-parts/][https_leetcode.com_problems_split-linked-list-in-parts]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

hint: If there are N nodes in the list, and k parts, then every part has N/k elements, except the first N%k parts have an extra one.

/** * 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) { 
            // 例1: 长度为10的链表, 分成3段, [4 3 3]
            // 其中，10%3=1段长度为4, 3-1=2段长度为3
            // 例2: 长度为11的链表, 分成3段, [4 4 3]
            // 其中，11%3=2段长度为4, 3-1=2段长度为3
            // 结论: 长度为L的链表, 分成k段, [a个"L/k向下取整", b个"L/k向上取整"]
            // 其中, a=L%k, b=k-b
            ListNode[] result = new ListNode[k];
            int L = 0;
            ListNode node = head;
            while (node != null) { 
                L++;
                node = node.next;
            }
            int floor = L / k;
            int ceil = (int) Math.ceil((float) L / k);
            int a = L % k;
            int b = k - a;
            // split
            int i = 0;
            ListNode pre = null;
            ListNode newHead = head;
            node = head;
            for (int j = 0; j < a; j++) { 
                for (int l = 0; l < ceil; l++) { 
                    pre = node;
                    node = node.next;
                }
                if (pre != null) pre.next = null;
                else newHead = null;
                result[i++] = newHead;
                newHead = node;
            }
            for (int j = 0; j < b; j++) { 
                for (int l = 0; l < floor; l++) { 
                    pre = node;
                    node = node.next;
                }
                if (pre != null) pre.next = null;
                result[i++] = newHead;
                newHead = node;
            }
            return result;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_split-linked-list-in-parts]: https://leetcode.com/problems/split-linked-list-in-parts/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/31f09b23ee094667be11bfc0a4a054e6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/13f65a16f91e4d72835c2531a46fe43a.png