✅ 99.10% Easy Linked List
Interview Guide - Splitting a Linked List into K Consecutive Parts: A Detailed Analysis\n\n## Introduction & Problem Understanding\n\nThe problem requires us to
# Interview Guide - Splitting a Linked List into K Consecutive Parts: A Detailed Analysis\n\n## Introduction & Problem Understanding\n\nThe problem requires us to split a singly-linked list into $$ k $$ consecutive parts. Each part should have nearly equal length, differing at most by 1. The parts should be in the same order as they appear in the original list, and parts occurring earlier should have a size greater than or equal to parts occurring later.\n\n### Key Concepts and Constraints\n\n1. **Node Anatomy**:  \n   Each node in the list has an integer value and a `next` pointer pointing to the subsequent node.\n\n2. **Equal Partition**:  \n   The linked list should be partitioned into $$ k $$ parts such that the size of each part is nearly equal.\n\n3. **Order Preservation**:  \n   The relative order of the elements within each part should be the same as in the original list.\n\n4. **Size Constraints**:  \n   The number of nodes in the list is between [0, 1000], and $$ k $$ is between [1, 50].\n\n## Live Codgin & More\nhttps://youtu.be/hcHz4HVEpvQ?si=hZFjiJU7n-qRb3Aw\n\n## Strategy to Tackle the Problem\n\n### Intuition and Logic Behind the Solution\n\nThe core idea is to first calculate the length of the linked list to determine the base size of each part and the number of parts that should have an extra node. Then, we traverse the list to construct each part based on these calculations.\n\n### Step-by-step Explanation\n\n1. **Initialization**:\n    - Initialize a variable `length` to store the length of the list.\n    - Initialize an empty list `parts` to store the resulting parts.\n\n2. **Calculate Length**:  \n    - Traverse the linked list to find its length.\n\n3. **Divide Length**:\n    - Calculate `base_size` and `extra` using `divmod(length, k)`.\n\n4. **Create Parts**:  \n    - Traverse the linked list again.\n    - For each part, construct a sublist with `base_size` nodes.\n    - If `extra > 0`, add one more node to the current part and decrement `extra`.\n\n5. **Append to Result**:  \n    - Append each constructed part to the `parts` list.\n\n### Complexity Analysis\n\n- **Time Complexity**: $$ O(n) $$ \u2014 The list is traversed twice: once to calculate its length and once to create the parts.\n- **Space Complexity**: $$ O(k) $$ \u2014 The `parts` list stores $$ k $$ heads of the resulting parts.\n\n## Code Highlights\n\n- The `divmod` function is used to calculate both `base_size` and `extra` in one line.\n- A dummy node is used to easily construct each part without special handling for the first node.\n- The `extra` variable is decremented directly in the loop where parts are constructed, avoiding the need for additional logic outside the loop.\n\nThis solution efficiently handles the constraints and requirements of the problem, offering a clean and effective way to split a linked list into $$ k $$ consecutive parts.\n\n# Performance\n\n| Language  | Execution Time (ms) | Memory Usage (MB) |\n|-----------|---------------------|-------------------|\n| **Java**  | **0**               | 43.7              |\n| Rust      | 1                   | 2.2               |\n| Go        | 3                   | 2.8               |\n| PHP       | 3                   | 19.6              |\n| C++       | 4                   | 9                 |\n| Python3   | 32                  | 16.8              |\n| JavaScript| 56                  | 45.2              |\n| C#        | 122                 | 43.8              |\n\n![mb2.png](https://assets.leetcode.com/users/images/443f5f05-5dd0-4b75-8fe4-55c952608618_1693963259.3068073.png)\n\n\n# Code\n``` Python []\nclass Solution:\n    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:\n        length, current, parts = 0, head, []\n        \n        while current:\n            length += 1\n            current = current.next\n        \n        base_size, extra = divmod(length, k)\n        current = head\n        \n        for _ in range(k):\n            dummy = ListNode()\n            part_head = dummy\n            \n            for _ in range(base_size + (extra > 0)):\n                dummy.next, current, dummy = current, current.next, current\n            \n            if extra > 0:\n                extra -= 1\n  \n            dummy.next = None\n            parts.append(part_head.next)\n        \n        return parts\n```\n``` Go []\nfunc splitListToParts(head *ListNode, k int) []*ListNode {\n    length := 0\n    current := head\n    var parts []*ListNode\n\n    for current != nil {\n        length++\n        current = current.Next\n    }\n\n    baseSize, extra := length/k, length%k\n    current = head\n\n    for i := 0; i < k; i++ {\n        partSize := baseSize\n        if extra > 0 {\n            partSize++\n            extra--\n        }\n\n        var partHead, partTail *ListNode\n\n        for j := 0; j < partSize; j++ {\n            if partHead == nil {\n                partHead, partTail = current, current\n            } else {\n                partTail.Next = current\n                partTail = partTail.Next\n            }\n\n            if current != nil {\n                current = current.Next\n            }\n        }\n\n        if partTail != nil {\n            partTail.Next = nil\n        }\n\n        parts = append(parts, partHead)\n    }\n\n    return parts\n}\n```\n``` Rust []\nimpl Solution {\n    pub fn split_list_to_parts(head: Option<Box<ListNode>>, k: i32) -> Vec<Option<Box<ListNode>>> {\n        let mut length = 0;\n        let mut current = head.as_ref();\n        let mut parts = Vec::new();\n        \n        while let Some(node) = current {\n            length += 1;\n            current = node.next.as_ref();\n        }\n        \n        let (mut base_size, mut extra) = (length / k, length % k);\n        let mut current = head;\n        \n        for _ in 0..k {\n            let mut part_size = base_size + if extra > 0 { 1 } else { 0 };\n            let mut dummy = Box::new(ListNode { val: 0, next: None });\n            let mut tail = &mut dummy;\n            \n            while part_size > 0 {\n                tail.next = current.take();\n                tail = tail.next.as_mut().unwrap();\n                current = tail.next.take();\n                part_size -= 1;\n            }\n            \n            parts.push(dummy.next.take());\n            if extra > 0 {\n                extra -= 1;\n            }\n        }\n        \n        parts\n    }\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    vector<ListNode*> splitListToParts(ListNode* head, int k) {\n        int length = 0;\n        ListNode* current = head;\n        vector<ListNode*> parts;\n\n        while (current) {\n            length++;\n            current = current->next;\n        }\n\n        int base_size = length / k, extra = length % k;\n        current = head;\n\n        for (int i = 0; i < k; ++i) {\n            int part_size = base_size + (extra > 0);\n            ListNode* part_head = nullptr, * part_tail = nullptr;\n\n            for (int j = 0; j < part_size; ++j) {\n                if (!part_head) {\n                    part_head = part_tail = current;\n                } else {\n                    part_tail->next = current;\n                    part_tail = part_tail->next;\n                }\n\n                if (current) {\n                    current = current->next;\n                }\n            }\n\n            if (part_tail) {\n                part_tail->next = nullptr;\n            }\n\n            parts.push_back(part_head);\n            extra = max(extra - 1, 0);\n        }\n\n        return parts;\n    }\n};\n```\n``` Java []\npublic class Solution {\n    public ListNode[] splitListToParts(ListNode head, int k) {\n        int length = 0;\n        ListNode current = head;\n        List<ListNode> parts = new ArrayList<>();\n\n        while (current != null) {\n            length++;\n            current = current.next;\n        }\n\n        int base_size = length / k, extra = length % k;\n        current = head;\n\n        for (int i = 0; i < k; i++) {\n            int part_size = base_size + (extra > 0 ? 1 : 0);\n            ListNode part_head = null, part_tail = null;\n\n            for (int j = 0; j < part_size; j++) {\n                if (part_head == null) {\n                    part_head = part_tail = current;\n                } else {\n                    part_tail.next = current;\n                    part_tail = part_tail.next;\n                }\n\n                if (current != null) {\n                    current = current.next;\n                }\n            }\n\n            if (part_tail != null) {\n                part_tail.next = null;\n            }\n\n            parts.add(part_head);\n            extra = Math.max(extra - 1, 0);\n        }\n\n        return parts.toArray(new ListNode[0]);\n    }\n}\n```\n``` C# []\npublic class Solution {\n    public ListNode[] SplitListToParts(ListNode head, int k) {\n        int length = 0;\n        ListNode current = head;\n        List<ListNode> parts = new List<ListNode>();\n\n        while (current != null) {\n            length++;\n            current = current.next;\n        }\n\n        int base_size = length / k, extra = length % k;\n        current = head;\n\n        for (int i = 0; i < k; i++) {\n            int part_size = base_size + (extra > 0 ? 1 : 0);\n            ListNode part_head = null, part_tail = null;\n\n            for (int j = 0; j < part_size; j++) {\n                if (part_head == null) {\n                    part_head = part_tail = current;\n                } else {\n                    part_tail.next = current;\n                    part_tail = part_tail.next;\n                }\n\n                if (current != null) {\n                    current = current.next;\n                }\n            }\n\n            if (part_tail != null) {\n                part_tail.next = null;\n            }\n\n            parts.Add(part_head);\n            extra = System.Math.Max(extra - 1, 0);\n        }\n\n        return parts.ToArray();\n    }\n}\n```\n\n``` JavaScript []\nvar splitListToParts = function(head, k) {\n    let length = 0, current = head, parts = [];\n\n    while (current) {\n        length++;\n        current = current.next;\n    }\n\n    let base_size = Math.floor(length / k), extra = length % k;\n    current = head;\n\n    for (let i = 0; i < k; i++) {\n        let part_size = base_size + (extra > 0 ? 1 : 0);\n        let part_head = null, part_tail = null;\n\n        for (let j = 0; j < part_size; j++) {\n            if (!part_head) {\n                part_head = part_tail = current;\n            } else {\n                part_tail.next = current;\n                part_tail = part_tail.next;\n            }\n\n            if (current) {\n                current = current.next;\n            }\n        }\n\n        if (part_tail) {\n            part_tail.next = null;\n        }\n\n        parts.push(part_head);\n        extra = Math.max(extra - 1, 0);\n    }\n\n    return parts;\n};\n```\n``` PHP []\nclass Solution {\n    function splitListToParts($head, $k) {\n        $length = 0;\n        $current = $head;\n        $parts = [];\n\n        while ($current) {\n            $length++;\n            $current = $current->next;\n        }\n\n        $base_size = intdiv($length, $k);\n        $extra = $length % $k;\n        $current = $head;\n\n        for ($i = 0; $i < $k; $i++) {\n            $part_size = $base_size + ($extra > 0 ? 1 : 0);\n            $part_head = $part_tail = null;\n\n            for ($j = 0; $j < $part_size; $j++) {\n                if ($part_head === null) {\n                    $part_head = $part_tail = $current;\n                } else {\n                    $part_tail->next = $current;\n                    $part_tail = $part_tail->next;\n                }\n\n                if ($current) {\n                    $current = $current->next;\n                }\n            }\n\n            if ($part_tail) {\n                $part_tail->next = null;\n            }\n\n            array_push($parts, $part_head);\n            $extra = max($extra - 1, 0);\n        }\n\n        return $parts;\n    }\n}\n```\n\nThis problem serves as a gentle reminder that sometimes, the most straightforward approach, when executed with precision, can be the most effective. Each node matters, each part matters, and how we traverse and split them, matters. Challenges like these don\'t just test our coding skills but enhance our problem-solving acumen. Code on, and let each node lead you to the solution! \uD83C\uDF1F\uD83D\uDE80
['Linked List', 'PHP', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'JavaScript', 'C#']