Split a Linked List into k Parts

Problem Statement

Given the head of a singly linked list and an integer k, split the linked list into k consecutive parts. The length of each part should be as equal as possible. If the length of the list is not divisible by k, then the first few parts should have one more node than the others.

Examples

Example 1:

Input: Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10, k = 3
Output: 
Part 1: 1 -> 2 -> 3 -> 4
Part 2: 5 -> 6 -> 7
Part 3: 8 -> 9 -> 10

Example 2:

Input: Linked List: 1 -> 2 -> 3, k = 5
Output: 
Part 1: 1
Part 2: 2
Part 3: 3
Part 4: nullptr
Part 5: nullptr

Approaches

1️⃣ 

Approach:

To solve this problem, follow these steps:

1. Calculate the Length of the Linked List: Traverse the linked list to calculate its total length n.
2. Determine the Size of Each Part:
   • The base size of each part is n / k.
   • The number of parts that need an extra node is n % k (remainder when n is divided by k).
3. Split the Linked List:
   • Traverse the linked list again and break it into parts.
   • For each part, keep track of the number of nodes needed and cut the list accordingly.
   • Store the head of each part in an array.

Code:

#include <iostream>
#include <vector>
using namespace std;

class ListNode {
public:
    int val;
    ListNode* next;

    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to split the linked list into k parts
vector<ListNode*> splitListToParts(ListNode* head, int k) {
    vector<ListNode*> parts(k, nullptr);
    int length = 0;
    ListNode* current = head;

    // Calculate the total length of the linked list
    while (current != nullptr) {
        length++;
        current = current->next;
    }

    // Determine the size of each part
    int partSize = length / k;
    int remainder = length % k;  // Extra nodes to distribute

    current = head;
    for (int i = 0; i < k && current != nullptr; i++) {
        parts[i] = current;  // Start of the current part
        int currentPartSize = partSize + (i < remainder ? 1 : 0);  // Extra node if i < remainder

        // Traverse current part size
        for (int j = 1; j < currentPartSize; j++) {
            current = current->next;
        }

        // Detach current part from the rest of the list
        ListNode* nextPart = current->next;
        current->next = nullptr;
        current = nextPart;
    }

    return parts;
}

// Helper function to print linked list parts
void printListParts(const vector<ListNode*>& parts) {
    for (int i = 0; i < parts.size(); i++) {
        ListNode* current = parts[i];
        cout << "Part " << i + 1 << ": ";
        while (current != nullptr) {
            cout << current->val << " -> ";
            current = current->next;
        }
        cout << "nullptr" << endl;
    }
}

// Example usage
int main() {
    // Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
    ListNode* head = new ListNode(1);
    ListNode* current = head;
    for (int i = 2; i <= 10; i++) {
        current->next = new ListNode(i);
        current = current->next;
    }

    int k = 3;
    vector<ListNode*> parts = splitListToParts(head, k);

    // Print the result
    printListParts(parts);

    return 0;
}

Part 1: 1 -> 2 -> 3 -> 4 -> nullptr
Part 2: 5 -> 6 -> 7 -> nullptr
Part 3: 8 -> 9 -> 10 -> nullptr

Explanation of Code:

1. Class Definition (ListNode):
   • Represents a node in the linked list, with an integer val and a pointer to the next node, next.
2. splitListToParts Function:
   • Calculates the length of the linked list.
   • Determines the base size of each part (partSize) and how many parts need an extra node (remainder).
   • Traverses the list to split it into k parts.
   • Stores the head of each part in the parts vector.
   • Cuts the list at appropriate positions to create the parts.
3. printListParts Function:
   • Utility function to print the contents of each part in the vector parts for verification.
4. main Function:
   • Demonstrates the creation of a linked list, splits it into parts using splitListToParts, and prints each part.

Complexity Analysis:

• Time Complexity:
  • O(n): The algorithm traverses the linked list twice. First, to calculate the length and then to split it into parts.
• Space Complexity:
  • O(k): Additional space is used for storing the parts in a vector of size k.