Leetcode No. 725. Split Linked List in Parts 📒

題號：No.725

類型：LinkedList

難度：medium

使用語言：JavaScript

¶題目

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.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

¶Example 1:

範例
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:

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.

¶Constraints:

• The number of nodes in the list is in the range [0, 1000].
• 0 <= Node.val <= 1000
• 1 <= k <= 50

---

¶解題切入的知識點

1. LinkedList 長度沒有內建的 function 可以使用，把取得長度的方式記起來!
2. 有點 tricky 是每組的長度判斷，先取最低值(Math.floor)，判斷剩下個數數量是否要加回數組長度
3. 放 node 回陣列逐一扣除數組長度後，要 handle 長度剩下 1 的狀況
4. 需要多宣告一個變數 t2 紀錄當前 head，並把 pointer 指向 null

---

¶解法

思考邏輯：

1. 首先要先求得 LinkedList 中 node 的個數，使用變數 n 紀錄 (沒有方法可以直接取得長度，沒有!!)
2. 接著要計算分成 k 組數的每組長度要多長，用 Math.floor 取得至少每組要有的個數 (無條件捨去，0.x 個 node 不能算一個)
3. 接著取得除以 k 組後剩餘的 node 個數
4. 迴圈從第一個數開始，要先判斷當前組數該放幾個數，判斷方法：剩餘的個數如果 > 0，組數長度+1，扣除一個剩餘組數
5. 宣告 t1 等於 root
6. 長度不為0要一直跑 while 迴圈
7. handle 假如長度只剩下1，宣告一變數 t2，t2 為當前 root，接著要接當前 root node 向前移動，t2 的 pointer 為 null (因為陣列長度只夠放下一個數字）
8. 假如長度不為0，root node 向下一個 node 移動，扣掉長度1
9. 把 t1 放回數組

 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode[]}
 */
var splitListToParts = function(head, k) {
    let temp = head
    let size = 0 // to record the linkedlist length
    
    // get length
    while(temp){
        size++
        temp = temp.next
    }
    
    let len = Math.floor(size / k) // each group length
    let realLen // to record the real length of each group 
    let cnt = size % k // remaining nodes
    let res = [] 
    
    for(let i = 0; i<k; i++){
        if(cnt > 0) {
            realLen = len + 1
            cnt --
        } else {
            realLen = len
        }
        
        let t1 = head //get the current node
        
        while(realLen > 0) { //put val to the array if the length 
            
           if(realLen === 1){
               let t2 = head
               head = head.next
               t2.next = null
           } else {
               head = head.next //keep iterating to the next node
           }  
            realLen --
        }
        res.push(t1)
    }
    return res
};