725. Split Linked List in Parts

T: O(n)

S: O(n)

Create new node:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] result = new ListNode[k];
        int len = 0;
        ListNode dummy = head;
        while (dummy != null) {
            len++;
            dummy = dummy.next;
        }
        int groupSize = len/k;
        int remainder = len%k;

        // use prev for cutting the end
        ListNode current = head;
        int idx = 0;

        while (current != null && idx < k) {
            ListNode dummyHead = new ListNode(0);
            ListNode tail = dummyHead;

            for (int i = 0; i < groupSize + (remainder > 0 ? 1 : 0); i++) {
                tail.next = new ListNode(current.val);
                tail = tail.next;
                current = current.next;
            }
            remainder--;
            result[idx++] = dummyHead.next;
        }
        return result;
    }
}

/**
T: O(n)
S: O(n)


occurring earlier should always "have a size greater than" or equal to parts occurring later.


find the whole len of list
3

3 / 5 = 0
3 % 5 = 3
1 1 1

10/3 = 3
10%3 = 1

3+1 3 3
 */

Don't create new Nodes:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] result = new ListNode[k];
        int len = 0;
        ListNode dummy = head;
        while (dummy != null) {
            len++;
            dummy = dummy.next;
        }
        int groupSize = len/k;
        int remainder = len%k;

        // use prev for cutting the end
        ListNode newHead = head;
        ListNode prev = null;
        int idx = 0;

        while (newHead != null && idx < k) {
            result[idx++] = newHead;
            for (int i = 0; i < groupSize + (remainder > 0 ? 1 : 0); i++) {
                prev = newHead;
                newHead = newHead.next;
            }
            prev.next = null;
            remainder--;
        }
        return result;
    }
}

/**
T: O(n)
S: O(n)


occurring earlier should always "have a size greater than" or equal to parts occurring later.


find the whole len of list
3

3 / 5 = 0
3 % 5 = 3
1 1 1

10/3 = 3
10%3 = 1

3+1 3 3
 */