diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /split_linked_list.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'split_linked_list.py')
-rw-r--r-- | split_linked_list.py | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/split_linked_list.py b/split_linked_list.py new file mode 100644 index 0000000..e73ee07 --- /dev/null +++ b/split_linked_list.py @@ -0,0 +1,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 |