725. Split Linked List in Parts

📝 Problem Details

• Title: 725. Split Linked List in Parts
• Link: https://leetcode.com/problems/split-linked-list-in-parts/
• Difficulty: Medium
• Tags/Categories: Linked-List

💭What Were My Initial Thoughts?

- we need to do an initial pass through of the list to find the length
- we need to calculate the number of nodes per part
- and calculate the number of extra nodes that will be leftover

🤔What Did I Struggle With?

- translating the above into code / algorithm
- use of the modulo operator in this case

💡 Explanation of Solution

1. calculate the total length: traverse the linked list first to get the total length

2. determine partition size:
	- calculate the base size for each part as `numNodes = len / k`
	- calculate the remainder as 'extra = len % k'
		- this represents the extra nodes that need to be distributed among the first `extra` parts
		- each of these will have numNodes + 1 elements

3. split the list
	- use a pointer temp to iterate through the list, to not lose the head which we will return 
	- create each part with numNodes elements
	- if there are remaining extra nodes, add one more node to the current part and decrement extra
	- after forming a part, set the next pointer of its last node to nullptr to detatch it from the remaining list

4. handle fewer nodes than k
	- if the list has fewer nodes than k, append nullptr to the result for the remaining parts

5. return result which should be a vector of linked lists representing the parts

⌛ Complexity Analysis

Time Complexity: O(n) as the list is traversed twice, once to compute the length and another to push nodes into their respective parts

Space Complexity: O(k) - a vector of size k is used to store the result

💻 Implementation of Solution

class Solution {
public:
	vector<ListNode*> splitListToParts(ListNode* head, int k) {
		int len = 0;
		ListNode* temp = head;
 
		while(temp) {
			len++;
			temp = temp->next;
		}
 
		int numNodes = len/k;
		int extra = len%k;
		int i = 0;
 
		vector<ListNode*> res;
		temp = head;
 
		while(temp) {
			res.push_back(temp);
			// get the numNodes and make the last node next to it NULL
			int currLen = 1;
 
			// construct our sublist
			while(currLen < numNodes) {
				temp = temp->next;
				currLen++;
			}
 
			if(extra > 0 && len > k) {
				temp = temp->next;
				extra--;
			}
 
			// detach the current part
			ListNode* x = temp->next;
			temp->next = nullptr;
			temp = x;
		}
 
		while(len < k) {
			res.push_back(nullptr);
			len++;
		}
 
		return res;
	}
}