SplitLinkedListInParts [source code]
public class SplitLinkedListInParts {
static
/******************************************************************************/
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode cur = root;
int length = 0;
while (cur != null) {
length++;
cur = cur.next;
}
int[] chunkLens = new int[k];
for (int i = 0; i < length; i++)
chunkLens[i % k]++;
ListNode[] res = new ListNode[k];
cur = root;
if (cur == null)
return res;
int pos = 0, chunkLen = chunkLens[pos];
res[pos] = new ListNode (cur.val);
ListNode chunk = res[pos];
while (cur != null) {
if (--chunkLen == 0) {
if ((cur = cur.next) == null)
break;
res[++pos] = new ListNode (cur.val);
chunk = res[pos];
chunkLen = chunkLens[pos];
} else {
cur = cur.next;
chunk.next = new ListNode (cur.val);
chunk = chunk.next;
}
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
SplitLinkedListInParts.Solution tester = new SplitLinkedListInParts.Solution();
int[][] inputs = {
{1,2,3,4},{5},
{1,2,3,4,5,6,7}, {3},
{}, {3},
};
int[][][] ans = {
{{1},{2},{3},{4},{}},
{{1,2,3},{4,5},{6,7}},
{{},{},{}},
};
for (int i = 0; i < inputs.length / 2; i++) {
ListNode root = ListNode.buildListNode (inputs[2 * i]);
int k = inputs[2 * i + 1][0];
System.out.println (Printer.separator ());
ListNode[] output = tester.splitListToParts (root, k);
String outputStr = Printer.array (output);
String ansStr = Printer.array (ListNode.buildListNodeArray (ans[i]));
System.out.printf ("[%s] and %d -> [%s], expected: [%s]\n",
root, k, Printer.wrapColor (outputStr, outputStr.equals (ansStr) ? "green" : "red"), ansStr
);
}
}
}
这个题目的一个难点是你不知道size; 所以笨办法就很简单, 直接先单独走一个pass得到size, 这样后面的分配数学上应该不难处理;
但是既然是一个medium的题目, 估计希望你能1pass走完?
另外这个题目的第二个example给的很好, 给出了一个细节上的展示, 到底怎么样才能保证满足题目给的size的要求;
想了半天并没有想到什么很聪明的做法, 看了一下hint, 好像并没有要求1pass做完, 那就直接开始写算了;
这题看起来是一个很简单的题目, 但是真正写起来就真的还没有那么trivial; 这题相比于一般的ListNode问题的一个难点在于, 这题需要实现一个分离的过程, 也就是你最后的结果是要你重新construct的; 这样就涉及到多个指针, 写起来就很绕脑子; 最后速度是6ms (10%).
另外这题对于Corner Case的考察其实也挺严厉的;
editorial
Approach #1: Create New Lists [Accepted]
class Solution {
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;
}
}
看完了之后真的是感叹我真的是有点死脑筋; 首先, 我count每一个chunk的长度的方法太死板, 还要一个一个的++, 实际上直接就可以计算出来, 你自己又不是不理解具体什么原理; 其次, 看他最后这个construct的过程, 比我的简练太多了! 我就是被一定要一个pass按顺序从头到尾走完这个观念, 或者说类似分段算法的思路给限制住了, 实际上按照他这个思路, 对每一个chunk, 分别进行一个construct就行了, 有什么难的呢? 而且完全不用像我的做法那样搞那么多的指针操作;
Approach #2: Split Input List [Accepted]
Intuition and Algorithm
As in Approach #1, we know the size of each part. Instead of creating new lists, we will split the input list directly and return a list of pointers to nodes in the original list as appropriate.
Our solution proceeds similarly. For a part of size L = width + (i < remainder ? 1 : 0), instead of stepping L times, we will step L-1 times, and our final time will also sever the link between the last node from the previous part and the first node from the next part.
class Solution {
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 = cur;
for (int j = 0; j < width + (i < rem ? 1 : 0) - 1; ++j) {
if (cur != null) cur = cur.next;
}
if (cur != null) {
ListNode prev = cur;
cur = cur.next;
prev.next = null;
}
ans[i] = head;
}
return ans;
}
}
这个是另外一个类似变形的做法, 注意看他这里这个break link的操作, 虽然实际上其实也不是特别的复杂;
discussion上面一个类似的split的做法:
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode[] parts = new ListNode[k];
int len = 0;
for (ListNode node = root; node != null; node = node.next)
len++;
int n = len / k, r = len % k; // n : minimum guaranteed part size; r : extra nodes spread to the first r parts;
ListNode node = root, prev = null;
for (int i = 0; node != null && i < k; i++, r--) {
parts[i] = node;
for (int j = 0; j < n + (r > 0 ? 1 : 0); j++) {
prev = node;
node = node.next;
}
prev.next = null;
}
return parts;
}
}
大概扫了一眼, 应该是能理解的;
discussion里面好像大部分的解法用的都是这种split的做法;
这个是submission最优解: 4(59):
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
if (root == null) return new ListNode[k];
if (k == 1) return new ListNode[]{root};
int len = 0;
ListNode point = root;
while (point != null) {
len++;
point = point.next;
}
ListNode[] res = new ListNode[k];
int shorted_length = len / k;
int number_of_longer_list = len % k;
point = root;
int cur_len = 0;
int index = 0;
while (point.next != null) {
cur_len++;
int extra_length = number_of_longer_list > 0 ? 1 : 0;
if (cur_len == shorted_length + extra_length) {
ListNode head = root;
res[index++] = head;
root = point.next;
point.next = null;
point = root;
cur_len = 0;
number_of_longer_list--;
} else {
point = point.next;
continue;
}
}
ListNode head = root;
res[index] = head;
return res;
}
}
大概思路其实是跟我的类似的, 只不过能优化的地方都优化了, 比如chunk_lens的计算, 然后是用split的办法来返回值而不是用construct的方法;
Problem Description
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.
Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]
Example 1:
Input: root = [1, 2, 3], k = 5 Output: [[1],[2],[3],[],[]] Explanation: The input and each element of the output are ListNodes, not arrays. For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null. The first element output[0] has output[0].val = 1, output[0].next = null. The last element output[4] is null, but it's string representation as a ListNode is [].
Example 2:
Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.
Note:
- The length of root will be in the range [0, 1000].
- Each value of a node in the input will be an integer in the range [0, 999].
- k will be an integer in the range [1, 50].
Difficulty:Medium
Total Accepted:5.9K
Total Submissions:12.1K
Contributor:swetjh
Companies
amazon
Related Topics
linked list
Similar Questions
Rotate ListOdd Even Linked List
Hint 1
If there are N nodes in the list, and k parts, then every part has N/k elements, except the first N%k parts have an extra one.