[LeetCode] 725. Split Linked List in Parts

https://leetcode.com/problems/split-linked-list-in-parts/description/?envType=daily-question&envId=2024-09-08

leetcode - Split Linked List in Parts

문제 유형 : 연결리스트

문제 난이도 : Medium

 

문제

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.

 

단순 연결리스트와 정수 k가 주어진다.

연결리스트를 k개의 부분으로 나눠서 배열에 담아라.

 

각 부분의 길이는 최대한 균등해야 하고, 많더라도 앞쪽이 뒤쪽보다 많아야 한다.

요소에 null이 오는 경우도 있을 수 있다. (연결리스트의 개수 < k)인경우

 

풀이

연결리스트를 한 번 순회해서 총 개수를 구한다.

기본적으로 분배할 개수 = n / k. = div

앞쪽에 1씩 더 분배할 칸의 개수: n % k = rest.

 

우선 배열의 0 ~ rest -1 칸에는 div+1개만큼 할당한다.

투 포인터로 curr, prev를 이용하여 div+1번 이동시키고, prev의 next를 null로 만든다.

 

나머지 rest ~ k칸에는 div개만큼 할당한다.

투 포인터로 curr, prev를 이용하여 div번 이동시키고, prev의 next를 null로 만든다.

 

혹시나 curr이 null에 도착해서 k칸보다 덜채워졌다면, 나머지 뒤에 null을 넣어주자.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        int n = 0;
        auto curr = head;
        while(curr != NULL) {
            n++;
            curr = curr -> next;
        }

        vector<ListNode*> ans;
        int rest = n % k;
        int div = n / k;

        curr = head;
        ListNode* prev;
        for(int i = 0; i < rest; i++) {
            ans.push_back(curr);
            for(int j = 0; j < div+1; j++) {
                prev = curr;
                curr = curr -> next;
            }
            prev -> next = NULL;
        }

        while(curr != NULL) {
            ans.push_back(curr);
            for(int j = 0; j < div; j++) {
                prev = curr;
                curr = curr -> next;
            }
            prev -> next = NULL;
        }

        for(int i = ans.size(); i < k; i++) {
            ans.push_back(NULL);
        }

        return ans;
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func splitListToParts(head *ListNode, k int) []*ListNode {
    n := 0
    curr := head

    for curr != nil {
        n++
        curr = curr.Next
    }

    rest := n % k
    div := n / k
    var prev *ListNode
    curr = head
    ans := make([]*ListNode, 0, k)

    for i := 0; i < rest; i++ {
        ans = append(ans, curr)
        for j := 0; j < div+1; j++ {
            prev = curr
            curr = curr.Next
        }
        prev.Next = nil
    }

    for curr != nil {
        ans = append(ans, curr)
        for j := 0; j < div; j++ {
            prev = curr
            curr = curr.Next
        }
        prev.Next = nil
    }

    for i := len(ans); i < k; i++ {
        ans = append(ans, nil)
    }

    return ans
}