131일 (725. Split Linked List in Parts) 연결리스트 조작

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

 

- 접근방법

 

만약 head의 총 길이를 n, k = 3일때 ListNode[]는 k개의 연결리스트가 구성된다.

그리고 각 연결리스트는 (n / k)개의 노드로 구성되며, (n % k)번 각 연결리스트에 노드를 1개씩 추가한다.

마지막으로 ListNode[]를 리턴한다.

→ head = [1, 2, 3, 4, 5, ,6, 7, 8, 9, 10, 11, 12, 13, 14], k =3 일때 n = 14가 된다.

ListNode array = ListNode[k]가 되고, array[0] ~ array[k-1]은 각각 (14 / 3 = 4) 개의 노드들로 구성된다.

그리고 (14 % 3 = 2)번 각 연결리스트에 노드가 1개씩 추가된다.

마지막으로 array = {{1,2,3,4,5}, {6,7,8,9,10}, {11,12,13,14}}가 되고 array를 리턴하면 된다.

 

 

1. head가 비어있다면 k개의 연결리스트로 구성된 배열을 리턴한다. (그러나 연결리스트에 포함되는 노드들은 없다.)

 

2. head의 총 길이인 n을 구한다.

 

3. head의 길이를 구했으므로 각 연결리스트를 구성하는 평균노드의 개수 avgNodeCount를 구하고, 각 연결리스트에 노드를 1개씩 더 추가하는 횟수 sumNodeCount를 구한다.

 

4. head가 null이 아닐때만 각 연결리스트에 필요한 평균 노드 개수를 추가한다.

5. sumNodeCount > 0 일때 노드를 1개씩 더 추가한다.

 

6. 각 연결리스트에 필요한 노드가 모두 추가되었으므로 ListNode[]에 현재 연결리스트를 추가한다. (k번 반복한다.)

 

 

- 코드

/**
 * 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) {
        ListNode[] answer = new ListNode[k];
        ListNode tempNode = head;
        int n = 1;

        if(head == null) return new ListNode[k]; // 1

        while(tempNode.next != null) { // 2
            tempNode = tempNode.next;
            n++;
        }

        int avgNodeCount = n/k; // 3
        int sumNodeCount = n%k;

        for(int i = 0; i < k; i++) {
            ListNode tempHead = new ListNode();
            tempNode = tempHead;

            for(int j = 0; j < avgNodeCount; j++) { // 4
                if(head != null) {
                    tempNode.next = new ListNode(head.val);
                    tempNode = tempNode.next;
                }
                head = head.next;
            }

            if(sumNodeCount > 0) { // 5
                if(head != null) {
                    tempNode.next = new ListNode(head.val);
                    tempNode = tempNode.next;
                }
                head = head.next;
                sumNodeCount--;
            }
            answer[i] = tempHead.next; // 6
        }

        return answer;
    }
}

 

연결리스트는 인덱스가 없으므로, 순회시 head의 정보를 기억하는 포인터 역할의 노드를 따로 만들어주어야한다.

현재노드가 null일 경우 아닐 경우를 명시해야 nullpointerException을 피할 수 있다.

ListNode의 next는 이미 선언이 되어있기 때문에 초기화만 하면 된다.

등등 다른 특징들은 많지만 주어지는 ListNode 클래스를 만지다보면 금방 익숙해진다.

 

 

 

 

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

LeetCode - The World's Leading Online Programming Learning Platform