725. Split Linked List in Parts

題目敘述

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

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.

題目翻譯

給定兩個參數，參數 head 是一個 Linked List，和一個參數 k 是一個整數。此題會需要的就是將 head 拆分成 k 個。如果有沒有辦法平分的部分，就從第一組開始分配。例如範例二，沒辦法將 head 平等拆成三份，就將多出來的放到第一個 [1, 2, 3, 4]。

解法解析

這題的解法，會先需要找出餘數，這樣才知道需要另外處理的部分，所以這邊會用一個迴圈來處理大概會是 O(n)。然後再用雙層的迴圈做拆分，第一層迴圈遍歷需要拆分的份數 O(k)，第二層則是遍歷 head，將拆分的結果儲存起來，這邊要特別就是判斷餘數，看是不是有多餘的部分要處理。

Time complexity：O(N + k). Space complexity：O(k)

程式範例

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
        cur = head
        for N in range(1001):
            if not cur:
                break
            cur = cur.next
        width, remainder = divmod(N, k)

        ans = []
        cur = head
        for i in range(k):
            tmp = cur
            for _ in range(width + (i < remainder) - 1):
                if cur:
                    cur = cur.next
            if cur:
                cur.next, cur = None, cur.next
            ans.append(tmp)
        return ans

JavaScript

/**
 * 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 len = 0;
    let cur = head;
    while (cur) {
        ++len;
        cur = cur.next;
    }

    let remainder = 0;
    let width = Math.floor(len / k);
    if (width === 0) width = 1;
    else remainder = len % k;

    let result = [];
    cur = head;
    for (let i = 0; i < k; i++) {
        const tmp = cur;

        let j = 0;
        while (j < width + (i < remainder) - 1) {
            if (cur) {
                cur = cur.next;
            }
            j++;
        }

        if (cur) {
            const temp = cur.next;
            cur.next = null;
            cur = temp;
        }

        result.push(tmp);
    }
    return result;
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func splitListToParts(head *ListNode, k int) []*ListNode {
    len := 0
    for cur := head; cur != nil; cur = cur.Next {
        len++
    }

    width, remainder := len/k, len%k

    ans := make([]*ListNode, k)
    cur := head
    for i := 0; i < k && cur != nil; i++ {
        ans[i] = cur
        var rc int
        if remainder > 0 {
            rc = 1
        }

        for j := 1; j < width+rc; j++ {
            cur = cur.Next
        }

        remainder--
        t := cur.Next
        cur.Next = nil
        cur = t
    }

    return ans
}

Swift

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func splitListToParts(_ head: ListNode?, _ k: Int) -> [ListNode?] {
        var ret = [ListNode?]()
        var N = 0
        var node = head
        while node != nil {
            node = node!.next
            N += 1
        }

        var r = N % k, q = N / k

        var cur = head
        for i in 0..<k {
            ret.append(cur)
            var size = q + (i < r ? 1 : 0)
            var j = 1
            while j < size {
                cur = cur?.next
                j += 1
            }
            let next = cur?.next
            cur?.next = nil
            cur = next
        }

        return ret
    }
}

Kotlin

/**
 * Example: var li = ListNode(5) var v = li.`val` Definition for singly-linked list. class
 * ListNode(var `val`: Int) {
 *

• var next: ListNode? = null
• ```

• } */ class Solution { fun splitListToParts(head: ListNode?, k: Int): Array {

   val listSize = size(head)
  
   val splitSize = listSize / k
   val plusOne = listSize % k
  
   var itr = head
   val result = Array<ListNode?>(k) { null }
  
   for (i in 1..k) {
       result[i - 1] = itr
       itr = run(itr, splitSize - 1 + if (plusOne >= i) 1 else 0)
       val next = itr?.next
       itr?.next = null
       itr = next
   }
  
   return result
  

  }

  private fun size(head: ListNode?): Int {

   var count = 0
   var itr = head
  
   while (itr != null) {
       itr = itr.next
       count++
   }
  
   return count
  

  }

  private fun run(head: ListNode?, num: Int): ListNode? {

   var itr = head
   repeat(num) { itr = itr?.next }
   return itr
  

  } } ```