# 725. Split Linked List in Parts

Question link is here.

# DescriptionGiven the `head` of a singly linked list and an integer `k`, split the linked list into `k` consecutive linked list parts.

The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

Example 1:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].

Example 2:

Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3
Output: [[1,2,3,4],[5,6,7],[8,9,10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

# Solution

# First Solution

There could be two solutions here. The first one is creating a new list first. And we travers the list to obtian the length of the list. And we calculate how long each parts suppose to have. And traverse the list again while copying each node. And put it the the result.

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int length = 0;
        ListNode node = head;
        while(node != null) {
            node = node.next;
            length = length + 1;
        }
        int segmentLength = length / k;
        int mod = length % k;
        node = head;
        ListNode[] ans = new ListNode[k];
        for(int i = 0; i < k; i++) {
            ListNode start = new ListNode(-1);
            ListNode temp = start;
            for(int j = 0; j < segmentLength + (i < mod ? 1 : 0); j++) {
                temp.next = new ListNode(node.val);
                temp = temp.next;
                if(node != null)
                    node = node.next;
            }
            ans[i] = start.next;
        }
        return ans;
    }
}

Time Complexity: $O(N+k)$

Space Complexity: $O(max(N, K))$

# Second Solution

The previous solution require extra space to store the new list, and this solution is a optimal space complexity.

Instead of creating a new list, we can put the head of each part to the result while doing the second traverse.

Note that since we need to cut the list, we need to make sure that the next pointer of last node in each part need to point to null.

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int length = 0;
        ListNode node = head;
        while(node != null) {
            node = node.next;
            length = length + 1;
        }
        int segmentLength = length / k;
        int mod = length % k;
        node = head;
        ListNode[] ans = new ListNode[k];
        for(int i = 0; i < k; i++) {
            ans[i] = node;
            for(int j = 0; j < segmentLength + (i < mod ? 1 : 0) - 1; j++) {
                if(node != null)
                    node = node.next;
            }
            if(node != null) {
                ListNode temp = node;
                node = node.next;
                temp.next = null;
            }
        }
        return ans;
    }
}

Time Complexity: $O(n+k)$

Space Complexity: $O(k)$

Leetcode 725

Split Linked List in Parts

# 725. Split Linked List in Parts

# DescriptionGiven the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

# Solution

# First Solution

# Second Solution

# DescriptionGiven the `head` of a singly linked list and an integer `k`, split the linked list into `k` consecutive linked list parts.