Split Linked List in Parts — Even Distribution

Sanjeev SharmaSanjeev Sharma
2 min read

Advertisement

Problem 234 · Split Linked List in Parts

Difficulty: Medium · Pattern: Even Distribution

Solutions

# Python
def splitListToParts(head, k):
    # Count length
    n = 0; cur = head
    while cur: n += 1; cur = cur.next
    part_size, extra = divmod(n, k)
    res = []
    cur = head
    for i in range(k):
        res.append(cur)
        size = part_size + (1 if i < extra else 0)
        for _ in range(size - 1):
            if cur: cur = cur.next
        if cur:
            cur.next, cur = None, cur.next
    return res
// Java
public ListNode[] splitListToParts(ListNode head, int k) {
    int n = 0; ListNode cur = head;
    while (cur != null) { n++; cur = cur.next; }
    int size = n / k, extra = n % k;
    ListNode[] res = new ListNode[k];
    cur = head;
    for (int i = 0; i < k; i++) {
        res[i] = cur;
        int len = size + (i < extra ? 1 : 0);
        for (int j = 0; j < len-1; j++) if (cur != null) cur = cur.next;
        if (cur != null) { ListNode nxt = cur.next; cur.next = null; cur = nxt; }
    }
    return res;
}

Complexity

  • Time: O(n + k)
  • Space: O(k) for output array

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro