推 JerryChungYC: 大師 09/06 15:18
https://leetcode.com/problems/split-linked-list-in-parts/description/
725. Split Linked List in Parts
給你一個連結串列 head 和一個數字 k，我們要把該串列切成 k 個部分，並且
每個部分都要滿足條件：
1.每個部分的大小相差不超過一，例如：[1][2][3] 或 [1,2][3]
2.前面部分大小必須大於等於後面，例如：[1,2,3][4,5,6,7] 不行因為後面比較大
3.必須按照切分前的原始順序排列
Example 1:
https://assets.leetcode.com/uploads/2021/06/13/split1-lc.jpg
Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a
ListNode is [].
Example 2:
https://assets.leetcode.com/uploads/2021/06/13/split2-lc.jpg
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]]
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.
思路：
1.先算出串列共有幾個元素，然後用 size 算出 node 分成k等分之後會多出幾個，這些
多的都先給前面的，就可以找出每個陣列裡面共有幾個元素。
2.再遍歷一次串列並抓出每個部分的head加入到結果集，每次加完一部分就把前個node的
next砍斷。
3.返回結果集。
Java Code：
-----------------------------------------------------
class Solution {
public ListNode[] splitListToParts(ListNode head, int k) {
ListNode curr = head;
int size = 0;
while (curr != null) {
curr = curr.next;
size++;
}
int listSize = size / k;
int extra = size % k;
ListNode[] res = new ListNode[k];
int index = 0;
int currSize = 0;
curr = head;
ListNode prev = null;
while (curr != null) {
if (currSize == listSize + (extra > 0 ? 1 : 0)) {
extra--;
currSize = 0;
prev.next = null;
}
if (currSize == 0) {
res[index++] = curr;
}
currSize++;
prev = curr;
curr = curr.next;
}
return res;
}
}
-----------------------------------------------------
--
https://i.imgur.com/uiFto42.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1693983960.A.E3F.html