Daily Leetcoding Challenge 725. Split Linked List in Parts

여러 가지 일이 몰리면서 머리가 아픈 상황이지만 그래도 오늘도 한 문제를 풀었다. 앞으로 나는 어떻게 해야 할지 참 고민이 많다.

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

Split Linked List in Parts - LeetCode

직관

문제는 링크드리스트가 주어졌을 때 링크드 리스트를 k개 링크드 리스트로 나눠서 리턴하는 것이다. 각 파트의 크기는 1 이상 차이가 나면 안 된다. 그리고 파트에는 null이 있을 수 있다.

먼저 링크드리스트의 크기를 알아내면(size) 각 파트의 크기는 최소 bucket(size / k) 가 될 것이고, 나머지 size % k 가 있다면 각 파트의 사이즈는 bucket+1 씩이 될 것이다.

접근법

각 파트의 사이즈만큼 cur 포인터를 옮긴다. 다 옮긴 뒤에는 prev 노드에 이전 노드 값을 저장해뒀다가 prev.next = None 파트를 끊어준다.

복잡도

시간 복잡도는 링크드 리스트의 사이즈를 찾을 때 한 번, 파트를 만들 때 한 번 순회하기 때문에 O(n), 공간 복잡도는 O(1)이다.

코드

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def splitListToParts(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: List[ListNode]
        """
        size = 0
        cur = head
        while cur:
            cur = cur.next
            size += 1
        bucket = size // k
        mod = size % k
        cur = head
        result = []
        while cur or (len(result) < k):
            if not cur:
                result.append(cur)
                continue
            prev = None
            result.append(cur)
            for i in range(0, bucket):
                prev = cur
                cur = cur.next
            if mod > 0:
                prev = cur
                cur = cur.next
                mod -= 1
            prev.next = None
        return result