🚀 Java 100% time 0ms || C++ 6ms || Two Pass Solution
Problem Description\nYou are given the head of a singly linked list and an integer k. Your task is to split the linked list into k consecutive linked list parts
# Problem Description\nYou are given the head of a singly linked list and an integer `k`. Your task is to split the linked list into `k` consecutive linked list parts based on these rules :\n1. The **length** of each part should be as **equal** as possible.\n2. No two parts should have a size **differing** by more than **one**.\n3. The **order** of the parts in the output should match the order of occurrence in the input list.\n4. Parts occurring **earlier** in the input list should always have a size **greater** than or **equal** to parts occurring later.\n\n\n---\n\n\n# Approach\n1. Calculate the **length** of the linked list.\n```\nListNode cur = head;\nint listLength = 0;\nwhile (cur != null) {\n    listLength++;\n    cur = cur.next;\n}\n```\n\n2. Calculate the **extra** elements in some parts and the **base length** for each part.\n**In our problem**, we use **division** to figure out the ideal size for each part and **modulo** to see if there are any leftovers (extras) that need to be distributed among the parts. This helps us make the parts as equal in size as possible.\n\n```\nint extra = listLength % k;\nint partLength = listLength / k;\n```\n\n3. Initialize variables and the result array.\n\n4. Iterate through the linked list to split it into `k` parts each with length `s + 1`.\n`s` is calculated by `partLength - 1 + ((extra-- > 0) ? 1 : 0)`, which means the original partLength plus check if there extra node to put it in the current part and minus 1 for our refrence to make sure we are at the last node of current part.\n\n5. Return the array of k parts.\n\n\n---\n\n\n# Complexity\n- **Time complexity**:\nSince we are traversing the LinkedList twice, it is `2*N`. so time complexity is `O(N)`.\n\n- **Space complexity**:\nWe store `K` heads in our answer list then space complexity is `O(K)`.\n\n\n---\n\n\n# Code\n\n```C++ []\nclass Solution {\npublic:\n    vector<ListNode*> splitListToParts(ListNode* head, int k) {\n        ListNode *cur = head;\n        vector<ListNode*> answer(k) ;\n        int ptr = 0, listLength = 0;\n\n        // Calculate the length of the linked list\n        while (cur != nullptr) {\n            listLength++;\n            cur = cur->next;\n        }\n\n        // Calculate the extra elements in some parts\n        int extra = listLength % k;\n        // Calculate the base length for each part\n        int partLength = listLength / k;\n        cur = head;\n\n        while (cur != nullptr) {\n            answer[ptr++] = cur;\n            // Calculate the length of the current part\n            int currentLength = partLength - 1 + ((extra-- > 0) ? 1 : 0);\n\n            // Move the current pointer to the end of the current part\n            for (int i = 0; i < currentLength; i++)\n                cur = cur->next;\n\n            // Disconnect the current part from the next part\n            ListNode *temp = cur->next;\n            cur->next = nullptr;\n            cur = temp;\n        }\n        return answer;\n    }\n};\n```\n```Java []\nclass Solution {\n    public ListNode[] splitListToParts(ListNode head, int k) {\n        ListNode cur = head;\n        ListNode[] answer = new ListNode[k];\n        int ptr = 0, listLength = 0;\n\n        // Calculate the length of the linked list\n        while (cur != null) {\n            listLength++;\n            cur = cur.next;\n        }\n\n        // Calculate the extra elements in some parts\n        int extra = listLength % k;\n        // Calculate the base length for each part\n        int partLength = listLength / k;\n        cur = head;\n\n        while (cur != null) {\n            answer[ptr++] = cur;\n            // Calculate the length of the current part\n            int currentLength = partLength - 1 + ((extra-- > 0) ? 1 : 0);\n\n            // Move the current pointer to the end of the current part\n            for (int i = 0; i < currentLength; i++)\n                cur = cur.next;\n\n            // Disconnect the current part from the next part\n            ListNode temp = cur.next;\n            cur.next = null;\n            cur = temp;\n        }\n        return answer;\n    }\n}\n```\n
['Linked List', 'Math', 'C++', 'Java']