POTD: LEET CODE – 725. (Split Linked List in Parts)

To solve 725. Split Linked List in Parts, the goal is to split a linked list into k parts, where the length difference between the parts is at most 1. If the list length is not divisible by k, the first parts will have one more element than the later ones.

Plan

1. Get the Length of the Linked List: First, we calculate the total length of the linked list.
2. Calculate Base Part Size and Extras: We then compute the base size of each part and how many parts need an extra node.

• baseSize = Math.floor(length / k) gives the base size for each part.
• extras = length % k gives the number of parts that will have an extra node.

1. Split the List: Traverse the list, and split it into k parts accordingly. If a part should have an extra node, we add it to that part.

Example Code

// Definition for singly-linked list.
function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

/**
 * @param {ListNode} head - The head of the linked list
 * @param {number} k - The number of parts to split the list into
 * @return {ListNode[]} - An array of ListNode heads representing each part
 */
var splitListToParts = function(head, k) {
    // Step 1: Calculate the total length of the list
    let length = 0;
    let current = head;
    while (current !== null) {
        length++;
        current = current.next;
    }

    // Step 2: Determine the base size of each part and the extra nodes
    let baseSize = Math.floor(length / k);
    let extras = length % k;

    let result = [];
    current = head;

    // Step 3: Split the list into k parts
    for (let i = 0; i < k; i++) {
        let partSize = baseSize + (extras > 0 ? 1 : 0); // Extra node for first 'extras' parts
        extras--;

        if (current === null) {
            result.push(null); // If there are no more nodes, push null
        } else {
            let partHead = current; // Start of the current part
            let prev = null;

            // Traverse partSize nodes to split the list
            for (let j = 0; j < partSize; j++) {
                prev = current;
                current = current.next;
            }

            // Disconnect the current part from the rest of the list
            if (prev !== null) {
                prev.next = null;
            }

            // Add the current part to the result array
            result.push(partHead);
        }
    }

    return result;
};

Explanation

1. Calculate the Length: First, we iterate through the linked list to find its length. This is essential to know how to divide the list into parts.
2. Determine Part Sizes:

• We calculate baseSize = Math.floor(length / k), which gives the minimum number of nodes each part should have.
• We calculate extras = length % k, which gives the number of parts that need an extra node. The first extras parts will have one more node than the others.

1. Splitting the List:

• We iterate through the list k times, creating a new part for each iteration. Each part will have a size of either baseSize or baseSize + 1, depending on the remaining extras.
• We disconnect each part from the rest of the list by setting prev.next = null after we have traversed the required number of nodes for that part.

1. Handle Extra Null Parts: If k is greater than the length of the list, some parts will be empty (i.e., null). These empty parts are added to the result.