Split the Linked List into k consecutive linked list “parts”

Technology CommunityCategory: Linked ListsSplit the Linked List into k consecutive linked list “parts”
VietMX Staff asked 3 years ago
Problem

Given a (singly) linked list with head node root, write a function to 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 1. This may lead to some parts being null.
  • The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.
  • Return a List of ListNode’s representing the linked list parts that are formed

Example:

[1,2,3,4,5,6,7,8,9,10], k=3
ans = [ [1,2,3,4] [5,6,7] [8,9,10] ]
  • If there are N nodes in the linked list root, then there are N/k items in each part, plus the first N%k parts have an extra item. We can count N with a simple loop.
  • Now for each part, we have calculated how many nodes that part will have: width + (i < remainder ? 1 : 0). We create a new list and write the part to that list.
Implementation
public ListNode[] splitListToParts(ListNode root, int k) {
  ListNode cur = root;
  int N = 0;
  while (cur != null) {
    cur = cur.next;
    N++;
  }

  int width = N / k, rem = N % k;

  ListNode[] ans = new ListNode[k];
  cur = root;
  for (int i = 0; i < k; ++i) {
    ListNode head = new ListNode(0), write = head;
    for (int j = 0; j < width + (i < rem ? 1 : 0); ++j) {
      write = write.next = new ListNode(cur.val);
      if (cur != null) cur = cur.next;
    }
    ans[i] = head.next;
  }
  return ans;
}