725. Split Linked List in Parts #

题目 #

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

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

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

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

思路 #

代码 #

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. 确定链表长度 length */
        ListNode ptr = head;
        int length = 0;
        while (ptr != null) { length += 1; ptr = ptr.next; }
        
        /** 2. 声明指针数组 */
        ListNode[] result = new ListNode[k];
        
        /** 3. 对链表长度小于k的情况进行讨论 */
        if (length < k) {
            ptr = head;
            for (int i=0; i<k; i++) {
                result[i] = ptr;
                if (ptr != null) {
                    ListNode tmp = ptr.next;
                    ptr.next = null;
                    ptr = tmp;
                }
            }
        } 
        
        /** 4. 对链表长度大于k的情况进行讨论 */
        else {
            ptr = head;
            int interval = length / k;
            for (int i=0; i<length % k; i++) {
                result[i] = ptr;
                for (int j=0; j<interval+1; j++) {
                    if (j == interval) {
                        ListNode tmp = ptr.next;
                        ptr.next = null;
                        ptr = tmp;
                    } else ptr = ptr.next;
                }
            }
            for ( int i = length % k; i < k; i++) {
                result[i] = ptr;
                for (int j=0; j<interval; j++) {
                    if (j == interval - 1) {
                        ListNode tmp = ptr.next;
                        ptr.next = null;
                        ptr = tmp;
                    } else ptr = ptr.next;
                }
            }
        }
        return result;
    }
}