725. Split Linked List in Parts

• Time: $O(n)$
• Space: $O(1)$
  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 class Solution { public: vector splitListToParts(ListNode* root, int k) { vector ans(k); const int length = getLength(root); const int subLength = length / k; int remainder = length % k; ListNode* prev = nullptr; ListNode* head = root; for (int i = 0; i < k; ++i, --remainder) { ans[i] = head; for (int j = 0; j < subLength + (remainder > 0); ++j) { prev = head; head = head->next; } if (prev) prev->next = nullptr; } return ans; } private: int getLength(ListNode* root) { int length = 0; for (ListNode* curr = root; curr; curr = curr->next) ++length; return length; } }; 
  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 class Solution { public ListNode[] splitListToParts(ListNode root, int k) { ListNode[] ans = new ListNode[k]; final int length = getLength(root); final int subLength = length / k; int remainder = length % k; ListNode prev = null; ListNode head = root; for (int i = 0; i < k; ++i, --remainder) { ans[i] = head; for (int j = 0; j < subLength + (remainder > 0 ? 1 : 0); ++j) { prev = head; head = head.next; } if (prev != null) prev.next = null; } return ans; } private int getLength(ListNode root) { int length = 0; for (ListNode curr = root; curr != null; curr = curr.next) ++length; return length; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]: ans = [[] for _ in range(k)] length = 0 curr = root while curr: length += 1 curr = curr.next subLength = length // k remainder = length % k prev = None head = root for i in range(k): ans[i] = head for j in range(subLength + (1 if remainder > 0 else 0)): prev = head head = head.next if prev: prev.next = None remainder -= 1 return ans