LeetCode Entry

725. Split Linked List in Parts

08.09.2024 medium 2024 kotlin rust

Split LinkedList into k parts list

725. Split Linked List in Parts medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/728

Problem TLDR

Split LinkedList into k parts #medium #linked_list

Intuition

This is a test of how clean your code can be. Count first, split second.

Approach

• count in each bucket i is n / k + (n % k > i)
• Rust makes you feel helpless

Complexity

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

• Space complexity: \(O(k)\)

Code

    fun splitListToParts(head: ListNode?, k: Int): Array<ListNode?> {
        var n = 0; var curr = head
        while (curr != null) { n++; curr = curr.next }
        curr = head
        return Array(k) { i -> curr?.also {
                for (j in 2..(n / k + if (i < n % k) 1 else 0))
                    curr = curr?.next
                curr = curr?.next.also { curr?.next = null }
        }}
    }

    pub fn split_list_to_parts(mut head: Option<Box<ListNode>>, k: i32) -> Vec<Option<Box<ListNode>>> {
        let mut n = 0; let mut curr = &head;
        while let Some(curr_box) = curr { n += 1; curr = &curr_box.next }
        (0..k).map(|i| {
            let mut start = head.take();
            let mut x = &mut start;
            for j in 1..n / k + (n % k > i) as i32 {
                if let Some(x_box) = x { x = &mut x_box.next }
            }
            if let Some(x_box) = x { head = x_box.next.take() }
            start
        }).collect()
    }

    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        int n = 0; ListNode* curr = head;
        while (curr) { n++; curr = curr->next; }
        vector<ListNode*> res;
        for (int i = 0; i < k; i++) {
            res.push_back(head);
            curr = head;
            for (int j = 1; j < n / k + (n % k > i); j++)
                curr = curr->next;
            if (curr) { head = curr->next; curr->next = NULL; }
        }
        return res;
    }