Split Linked List in Parts

class Solution {
public:
    vector<ListNode*> distributeList(ListNode* root, int k) {
        vector<ListNode*> result(k);
            
        // Determine the total number of nodes
        int length = 0;
        ListNode* ptr = root;
        while (ptr != nullptr) {
            length++;
            ptr = ptr->next;
        }
    
        // Define base length of each part
        int baseLength = length / k;
    
        // Calculate the excess nodes to distribute
        int extraNodes = length % k;
    
        ptr = root;
        ListNode* lastNode = ptr;
        for (int i = 0; i < k; i++) {
            ListNode* partHead = ptr;
            int partLength = baseLength + (extraNodes-- > 0 ? 1 : 0);
                
            for (int j = 0; j < partLength; j++) {
                lastNode = ptr;
                if (ptr != nullptr) ptr = ptr->next;
            }
    
            // Detach the current part from next
            if (lastNode != nullptr) {
                lastNode->next = nullptr;
            }
    
            result[i] = partHead;
        }
    
        return result;
    }
};

The solution implements a function distributeList in C++ for splitting a linked list into k parts as evenly as possible. Each part should be in the form of a separate linked list and all parts should collectively use up all nodes of the original list.

Summary of the Approach:

• Begin by calculating the total number of nodes in the input linked list.
• Determine the base length that each part should have, which is the total number of nodes divided by k.
• Compute the number of extra nodes that need to be distributed one by one to the first few parts until exhausted. This is derived from the modulus of the total node count by k.
• Iterate over each part to allocate the nodes:
  • For each part, initialize with the base length.
  • If there are extra nodes, increase the length of the current part by one.
  • Detach each selected part from the main list after assigning the necessary nodes.
• Once all parts are processed, return the vector containing the head of each part.

Detailed Steps Involved:

1. First, traverse the whole linked list to count the total number of nodes.
2. Compute baseLength as the quotient of the node count divided by k.
3. Compute extraNodes as the remainder of the node count divided by k.
4. Initialize ptr to the head of the list to manage traversal, with lastNode helping in detachment later.
5. Loop over k parts, setting the partHead for each part:
   • Iterate over nodes for each part based on partLength, detach the end of the part, and continue to the next part.
   • Adjust the next pointer of lastNode to null to split the list.
   • Store the head node of the current part into the result vector.
6. After exiting the loop, return the result vector, containing the head nodes of each separate list part.

This approach efficiently manages the linked list nodes while maintaining correct pointers and evenly distributing nodes among the parts.

class Solution {
    
    public ListNode[] divideList(ListNode headNode, int partitions) {
        ListNode[] resultParts = new ListNode[partitions];
    
        // Calculate total nodes in list
        int totalNodes = 0;
        ListNode ptr = headNode;
        while (ptr != null) {
            totalNodes++;
            ptr = ptr.next;
        }
    
        // Base size of each part
        int basePartSize = totalNodes / partitions;
    
        // Extra nodes to distribute
        int extraNodes = totalNodes % partitions;
    
        ptr = headNode;
        ListNode temp = ptr;
        for (int i = 0; i < partitions; i++) {
            // Start a new part
            ListNode partHead = ptr;
            // Calculate nodes in this part
            int thisPartSize = basePartSize + (extraNodes > 0 ? 1 : 0);
            if (extraNodes > 0) extraNodes--;
    
            // Iterate to end of this part
            for (int j = 0; j < thisPartSize; j++) {
                temp = ptr;
                ptr = ptr.next;
            }
            // Disconnect this part from the rest
            if (temp != null) {
                temp.next = null;
            }
    
            resultParts[i] = partHead;
        }
    
        return resultParts;
    }
}

This Java solution tackles the problem of dividing a linked list into a given number of equal parts. It's designed to handle cases where the linked list can't be divided evenly by taking care to distribute the remainder nodes as uniformly as possible across the resulting parts.

• Start by initializing an array resultParts to store each part of the split linked list.
• Count the total number of nodes in the given linked list to help in evenly distributing nodes among the parts.
• Calculate the base size of each part using integer division of the total nodes by the number of partitions. Determine any extra nodes using the modulus operator.
• Traverse the linked list again, this time partitioning the nodes according to the calculated sizes. If there are extra nodes, incrementally add one extra node to the early parts until no extra nodes remain.
• For each part, traverse the desired portion and then cleanly break off the part from the main list to ensure each part stands alone.
• Each node section determined by the respective indices in the loop is assigned to its position in the resultParts array.

By the end of these steps, resultParts holds each sublist in its respective order, providing a properly divided linked list.

class Solution:
    def divideLinkedList(
        self, head: Optional[ListNode], parts: int
    ) -> List[Optional[ListNode]]:
        result = [None] * parts
    
        # Calculate total elements
        length = 0
        node = head
        while node is not None:
            length += 1
            node = node.next
    
        # Basic part size
        base_size = length // parts
    
        # Extra nodes to distribute
        extra_nodes = length % parts
    
        node = head
        previous = node
        for part_index in range(parts):
            # Assign starting node of current part
            part_head = node
            # Compute size for this part
            part_length = base_size + (1 if extra_nodes > 0 else 0)
            if extra_nodes > 0:
                extra_nodes -= 1
    
            # Find end of current part
            for _ in range(part_length):
                previous = node
                if node:
                    node = node.next
                
            # Detach current part from the rest of list
            if previous:
                previous.next = None
                
            result[part_index] = part_head
    
        return result

In the Python solution for splitting a linked list into parts, the given approach involves several clear steps:

1. Initialize a result list filled with None, with a length equal to the number of parts required.

2. Count the total number of elements in the linked list to determine the length.

3. Calculate the basic size of each part by performing an integer division of the total length by the number of parts.

4. Determine the number of nodes that need to be extra distributed, which is found by computing the remainder of the total length and the number of parts.

5. The linked list is then traversed, and for each part, a new segment of the linked list is defined starting from the current head node.

6. Adjust the length for each part based on whether there are extra nodes available. If there are extra nodes, one node is added to the current part and the count of extra nodes is decremented.

7. Traverse each segment of the linked list corresponding to the adjusted length, and detach it properly by setting the next pointer of the last node in the current segment to None.

By following this method, the linked list is divided into the specified number of parts, where each part is either of equal length or the first few parts have one more node than the others, depending on how the nodes distribute. This approach ensures each part is as balanced as possible given the constraints of the node count and requested parts.