LeetCode Entry

725. Split Linked List in Parts

6.09.2023 medium 2023 kotlin

Split Linked List into k almost equal lists

725. Split Linked List in Parts medium blog post substack

image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/331

Problem TLDR

Split Linked List into k almost equal lists

Intuition

First, precompute sizes, by adding to buckets one-by-one in a loop. Next, just move list pointer by sizes values.

Approach

Do not forget to disconnect nodes.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\) for the sizes array and for the result

Code


    fun splitListToParts(head: ListNode?, k: Int): Array<ListNode?> {
      val sizes = IntArray(k)
      var i = 0
      var curr = head
      while (curr != null) {
        sizes[i++ % k]++
        curr = curr.next
      }
      curr = head
      return sizes.map { sz ->
        curr.also {
          repeat(sz - 1) { curr = curr?.next }
          curr = curr?.next.also { curr?.next = null }
        }
      }.toTypedArray()
    }