[leetcode # 725] Split Linked List in Parts

Problem

Given 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.

Constraints:

・ The number of nodes in the list is in the range [0, 1000].
・ 0 <= Node.val <= 1000
・ 1 <= k <= 50

Idea

주어진 리스트를 k개로 나누어 array에 저장한 뒤 리턴하라는 문제다. 단, k개로 나눴을 때 나눈 list의 개수 차이는 한 개가 최대가 되어야하며, array의 앞쪽에 오는 리스트의 크기가 뒤쪽에 오는 리스트의 크기보다 크거나 같아야 한다.

우선 주어진 리스트의 길이를 구한다. 리스트의 길이를 k로 나눈 몫과 나머지를 구한다. 리스트를 나눌 때 나머지가 0보다 크다면 (몫+1)이 해당 리스트의 크기가 되며, 그렇지 않을 경우 몫이 리스트의 크기가 된다. 리스트를 나눌 때마다 나머지를 1씩 빼준다. 이런 식으로 리스트를 나누면 위에서 말한 조건을 충족한 array가 만들어진다.

알고리즘은 다음과 같다.

1. list의 크기를 구한다.
2. list의 크기를 k로 나눈 몫과 나머지를 구한다.
3. list를 k개로 나누어 array에 저장한다. 나머지가 0보다 클 경우 (몫+1)개 만큼의 node를 넣어주며, 그렇지 않을 경우 몫과 같은 개수의 node를 넣어준다.array에 저장한 뒤 나머지는 1씩 감소시킨다.
4. 만들어진 array를 리턴한다.

Solution

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
    	// 1. list의 크기를 구한다
    	ListNode node = head;
        int length = 0;
        while (node != null) {
            length++;
            node = node.next;
    	}
       
	// 2. list의 크기를 k로 나눈 몫과 나머지를 구한다.
        int quotient = length / k;
        int remainder = length % k;
        ListNode[] listNode = new ListNode[k];

	// 3. 리스트를 k개로 나눈다. 루프를 돌며 나머지를 1씩 빼주며, 나머지가 0보다 클 경우 리스트의 크기는 몫+1이 된다.    
        node = head;
        int index = 0;
        while (node != null) {
            int size = remainder > 0 ? quotient + 1 : quotient;
            listNode[index++] = node;
            ListNode prev = null;
            for (int i=0; i < size; i++) {
                prev = node;
                node = node.next;
            }
            if (prev != null)
                prev.next = null;

            remainder--;
        }
   
        return listNode;
    }
}

Reference

https://leetcode.com/problems/split-linked-list-in-parts/