algoadvance

Leetcode 725. Split Linked List in Parts

Problem Statement

You are 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 distribute.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should never be smaller than parts occurring later.

Return an array of the k parts.

Example:

  1. Input:
    • head = [1, 2, 3], k = 5
    • Output: [[1], [2], [3], [], []]
  2. Input:
    • head = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
    • Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

Clarifying Questions

  1. What should be done if the input linked list is empty?
    • If the input list is empty, we should return an array with k empty parts.
  2. What should be the format of the output?
    • The output should be an array of linked list nodes.

Code

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        // Step 1: Find the total length of the linked list.
        int totalLength = 0;
        ListNode current = head;
        while (current != null) {
            totalLength++;
            current = current.next;
        }

        // Step 2: Determine the size of each part and the number of larger parts needed.
        int partSize = totalLength / k;
        int extraNodes = totalLength % k;

        ListNode[] result = new ListNode[k];
        current = head;
        for (int i = 0; i < k; i++) {
            ListNode dummy = new ListNode(0);
            ListNode write = dummy;
            // Determine how many nodes this part should contain
            int currentPartSize = partSize + (i < extraNodes ? 1 : 0);
            for (int j = 0; j < currentPartSize; j++) {
                write = write.next = new ListNode(current.val);
                if (current != null) {
                    current = current.next;
                }
            }
            result[i] = dummy.next;
        }

        return result;
    }
}

Strategy

  1. Find Total Length:
    • Traverse the linked list to calculate the total number of nodes in the list.
  2. Determine Part Sizes:
    • Calculate the size of each part. Each part ideally gets totalLength / k nodes. The first totalLength % k parts get one additional node each.
  3. Split the List:
    • Traverse the list again, this time splitting it into parts based on the sizes calculated earlier and store the sublists in an array.

Time Complexity

Do you have any specific questions or requirements about the approach?

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