aboutsummaryrefslogtreecommitdiff
path: root/split_linked_list.py
blob: e73ee07b808170bbc284f8633eadd7e265654e6b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 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 some parts being null. the parts should be in the
order of occurence in the input list, and parts occuring earlier should
always have a size greater than or equal to parts occuring later. return an
array of the 'k' parts.
"""


class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution(object):
    def splitListToParts(self, head, k):
        parts = [None] * k
        len = 0
        node = head
        while node:
            len += 1
            node = node.next
        n, r = divmod(len, k)
        node = root
        prev = None
        for i in range(k):
            parts[i] = node
            for j in range(n + (1 if r > 0 else 0)):
                prev = node
                node = node.next
            if prev:
                prev.next = None
            if r > 0:
                r -= 1
        return parts