medium Split Linked List in Parts

Problem Statement

Given a head of the singly linked list and integer k, split the list into k consecutive parts and return them.

The length of each part should not differ more than 1, and it may lead to some parts being null.

The order of parts should be the same as given in the input list, and parts in the start should have a size greater than or equal to the parts in the end.

Examples

Example 1:

• Input: head = [1, 2, 3, 4, 5, 6, 7], k = 3
• Expected Output: [[1, 2, 3], [4, 5], [6, 7]]
• Justification: The list of 8 elements is divided into 3 parts. The first part has 3 elements and the last two parts have 2 elements, distributing the nodes as evenly as possible.

Example 2:

• Input: head = [1, 2, 3], k = 4
• Expected Output: [[1], [2], [3], []]
• Justification: The list of 3 elements is divided into 4 parts, resulting in the first three parts having one element each and the last one part being empty, as there are fewer nodes than parts.

Example 3:

• Input: head = [1, 2, 3, 4, 5, 6, 7], k = 2
• Expected Output: [[1, 2, 3, 4], [5, 6, 7]]
• Justification: The list of 7 elements is divided into 2 parts. The first part contains 4 elements and the second part contains 3 elements, making the parts as equal in size as possible.

Solution

To solve this problem, we will first count the total number of nodes in the linked list. This count helps us determine the size of each part and how to distribute any extra nodes. Our approach ensures that each part has either floor(total nodes / k) or ceil(total nodes / k) nodes, where k is the number of parts we need to split the list into. We believe this approach is effective because it ensures a fair distribution of nodes across the parts, with any remainder nodes being evenly distributed from left to right, adhering to the problem's requirement.

Our algorithm will iterate through the linked list, creating new sub-lists based on the calculated sizes. For each part, we will detach nodes from the original list and link them together to form a part, ensuring to nullify the next pointer of the last node in each part to signify its end. This method is efficient as it requires only a single pass through the original list and carefully reallocates nodes to form the desired structure without altering their original order.

Step-by-step Algorithm

• Calculate the total number of nodes in the linked list, denoted as totalNodes.
• Determine the base size of each part as baseSize = totalNodes / k, and calculate the number of parts that need an extra node, extraNodes = totalNodes % k.
• Initialize a result array of linked lists with k elements.
• Traverse the linked list, for each part:
  • Determine the size of the current part, adding one extra node to the first extraNodes parts.
  • Create a new sub-list for the part by detaching the determined number of nodes from the original list.
  • Ensure the last node of the current part points to null to end the sub-list.
• Repeat the process until all parts are created or the list ends.
• Return the array of linked list parts.

Algorithm Walkthrough

Let's consider the input: head [1, 2, 3, 4, 5, 6, 7], k = 3.

Initial Setup

• Total number of nodes, totalNodes = 7.
• Calculate base size of each part, baseSize = totalNodes / k = 7 / 3 = 2 (since we're dealing with integers, the fraction is discarded).
• Calculate extra nodes, extraNodes = totalNodes % k = 7 % 3 = 1.
• Initialize an array to hold the result, parts, with a size of k = 3.

Iteration 1 (Part 1)

• Part size calculation: Since extraNodes > 0, the first part will have baseSize + 1 = 2 + 1 = 3 nodes.
• Nodes to include: Start from the first node and include the first 3 nodes in this part. The nodes are [1, 2, 3].
• Update extraNodes: After using one extra node, extraNodes = 0.
• Advance the pointer: Move the current pointer to the node after the last included node, which is node 4.

Iteration 2 (Part 2)

• Part size calculation: Now, extraNodes = 0, so this part will have only baseSize = 2 nodes.
• Nodes to include: Starting from the current node (4), include the next 2 nodes in this part. The nodes are [4, 5].
• Advance the pointer: Move the current pointer to the node after the last included node, which is node 6.

Iteration 3 (Part 3)

• Part size calculation: The size remains baseSize = 2. However, since we're at the last part and there are remaining nodes, include all remaining nodes in this part.
• Nodes to include: Starting from the current node (6), include the rest of the nodes in this part. The nodes are [6, 7].
• End of list: We've reached the end of the list and distributed all nodes among the parts.

Summary

• The linked list [1, 2, 3, 4, 5, 6, 7] is split into 3 parts as follows:
  • Part 1: [1, 2, 3]
  • Part 2: [4, 5]
  • Part 3: [6, 7]

Code

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

class Solution {

  public ListNode[] splitListToParts(ListNode root, int k) {
    // Step 1: Calculate the total length of the list
    int length = 0;
    ListNode current = root;
    while (current != null) {
      length++;
      current = current.next;
    }

    // Step 2: Determine the size of each part and any extra nodes that need to be distributed
    int partSize = length / k;
    int extra = length % k;

    // Step 3: Create an array to store the resulting parts
    ListNode[] parts = new ListNode[k];
    current = root;

    // Step 4: Iterate through each part
    for (int i = 0; i < k; i++) {
      ListNode head = current, tail = null;
      // Step 5: Traverse the current part size
      for (int j = 0; j < partSize + (i < extra ? 1 : 0); j++) {
        tail = current;
        current = current.next;
      }
      // Step 6: Cut off the current part from the remaining list
      if (tail != null) tail.next = null;
      // Step 7: Store the head of the current part in the result array
      parts[i] = head;
    }

    // Step 8: Return the resulting array of parts
    return parts;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    ListNode head1 = new ListNode(1);
    head1.next = new ListNode(2);
    head1.next.next = new ListNode(3);
    head1.next.next.next = new ListNode(4);
    head1.next.next.next.next = new ListNode(5);
    head1.next.next.next.next.next = new ListNode(6);
    head1.next.next.next.next.next.next = new ListNode(7);
    // Step 9: Call splitListToParts method with the given list and k value
    ListNode[] result1 = solution.splitListToParts(head1, 3);

    // Printing the output
    for (ListNode part : result1) {
      ListNode current = part;
      while (current != null) {
        System.out.print(current.val + " ");
        current = current.next;
      }
      System.out.println();
    }
  }
}

Complexity Analysis

Time Complexity

• Calculating the total length of the list: We traverse the entire list once to calculate its length, which takes time, where (n) is the number of nodes in the list.
• Splitting the list into parts: We again traverse the list to split it into (k) parts. This process also takes time since each node is visited only once during the splitting process.

Thus, the total time complexity is , as both operations are linear in terms of the number of nodes in the list.

Space Complexity

• Output Array: We create an output array to store the (k) parts and total (n) elements, which takes space.
• No extra space for nodes: We are not creating new nodes; we are only rearranging the pointers. Hence, there's no additional space complexity in terms of nodes.

Therefore, the total space complexity is , where (n) is the number of nodes in the list.