algoadvance

Leetcode 725. Split Linked List in Parts

Problem Statement

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 to some parts being null if there are not enough nodes to be distributed.

The resultant parts should be in the same order as they appeared in the original list.

Clarifying Questions

  1. Q: What should we return if k is greater than the number of nodes in the list? A: In such cases, the resulting list should have some empty parts (nullptr), and the existing nodes should be distributed one per part until the nodes are exhausted.

  2. Q: Can we modify the original linked list? A: Yes, breaking the next pointers to create separate lists is allowed.

  3. Q: How should we handle special cases such as an empty list or k equal to zero? A: If the list is empty or k is 0, the returned array should consist of k nullptr entries.

Strategy

  1. Count the number of nodes in the linked list.
  2. Calculate the guaranteed minimum size of each part and find out how many parts will need to take one extra node.
  3. Iterate through the list, cutting it into parts according to the calculated sizes.
  4. Store the heads of these parts in an array and return the array.

Detailed Steps:

  1. Count the Nodes: Traverse the list to count the total number of nodes.

  2. Determine the Size of Each Part:
    • Calculate the base size of each part as total_length / k.
    • Determine the remainder total_length % k to find out how many parts need an extra node.
  3. Split the List:
    • Use a loop to go through each part.
    • Create each part by breaking the next pointer at the appropriate positions.
  4. Form the Result: Form an array where each element corresponds to the head of a part in the list.

Code

#include <vector>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        // Step 1: Count the number of nodes in the list
        int total_length = 0;
        ListNode* temp = head;
        while (temp) {
            total_length++;
            temp = temp->next;
        }
        
        // Step 2: Determine the base size and remainder
        int base_size = total_length / k;
        int remainder = total_length % k;
        
        // Step 3: Split the list into parts
        vector<ListNode*> result(k, nullptr);
        ListNode* current = head;
        for (int i = 0; i < k && current; i++) {
            result[i] = current;
            int part_size = base_size + (i < remainder ? 1 : 0);
            
            // Advance to the end of the current part
            for (int j = 1; j < part_size; j++) {
                current = current->next;
            }
            
            // Break the list at the end of the current part
            ListNode* next = current->next;
            current->next = nullptr;
            current = next;
        }
        
        return result;
    }
};

Time Complexity

Thus, the overall time complexity is O(n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI