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

1. Split Input list:

  1. //8 ms    8.4 MB
  3. /**
  4.  * Definition for singly-linked list.
  5.  * struct ListNode {
  6.  *     int val;
  7.  *     ListNode *next;
  8.  *     ListNode() : val(0), next(nullptr) {}
  9.  *     ListNode(int x) : val(x), next(nullptr) {}
  10.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     vector<ListNode*> splitListToParts(ListNode* root, int k) {
  16.         vector<ListNode*> result;
  18.         int n = 0;
  19.         ListNode* curr = root;
  21.         //get the length of the list
  22.         while(curr){
  23.             curr = curr->next;
  24.             n++;
  25.         }
  27.         int width = n / k; //width of a block
  28.         int rest = n % k; //rest of elements
  30.         //cout << width << " " << rest << endl;
  32.         curr = root;
  34.         ListNode* head = curr;
  35.         ListNode* prev = curr;
  37.         for(int i = 0; i < k; i++){
  38.             head = curr;
  39.             for(int j = 0; j < width - 1 + (i < rest ? 1 : 0); j++){
  40.                 if(curr)
  41.                     curr = curr->next;
  42.             }
  43.             if(curr){
  44.                 prev = curr;
  45.                 curr = curr->next;
  46.                 prev->next = NULL;
  47.             }
  48.             result.push_back(head);
  49.         }
  51.         return result;
  52.     }
  53. };
  55. //about "width - 1 + (i < rest ? 1 : 0)"
  56. //if k > n, there is no enough space for each block to has at least 1 element
  57. //so that for example
  59. /*
  60. Input:
  61. root = [1, 2, 3], k = 5
  62. Output: [[1],[2],[3],[],[]]
  63. */
  64. //width = 1, rest = 3
  65. //when i < 3, j = 0, and j++ until j < (1 - 1 + 1), so curr only move 1 step at a time
  66. //when i >= 3, j = 0, and j++ until j < (1 - 1 + 0), so curr could not move anymore, and pushes empty lists
  68. /*
  69. Input: 
  70. root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
  71. Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
  72. */
  73. //width = 3, rest = 1
  74. //when i<1, j = 0, and j++ until j < (3 - 1 + 1), so curr moves 3 steps at a time
  75. //when i>=1, j = 0, and j++ until j < (3 - 1 + 0), so curr moves 2 steps at a time
  • Time Complexity: O(N + k), where N is the number of nodes in the given list. If k is large, it could still require creating many new empty lists.
  • Space Complexity: O(k), the additional space used in writing the answer.