Leetcode 725. Split Linked List in Parts

Problem Explanation

This problem is asking us to split a singly-linked list into k parts. We need to distribute the nodes almost equally in all parts such that the difference in the size between any two parts is a maximum of 1. Also, the parts occurring earlier should have more nodes in case of an uneven distribution.

Here's how we can approach this:

Firstly, we will traverse the entire linked list to get its length. Let's say the length of the linked list is length.

Subsequently, the size of each part will be length / k and the first length % k parts will contain one extra node. This is because, in case of an uneven distribution, the earlier parts should contain more nodes.

Then, we can simply create k linked lists with length / k nodes and the first length % k lists contain one extra node.

Let's go over an example:

Let's consider a Linked list 1 -> 2 -> 3 -> 4 -> 5 -> 6 and k = 4.

• Step 1: Get the length of the linked list which is 6 in this case.
• Step 2: Compute length / k = 6 / 4 = 1 and length % k = 6 % 4 = 2.
• Step 3: Distribute the nodes in 4 parts such that first 2 parts have 1+1 nodes and the remaining 4-2=2 parts have 1 node.
• Step 4: The 4 parts would be [1, 2], [3, 4], [5], [6].

Python Solution

1
2python
3class ListNode(object):
4    def __init__(self, x):
5        self.val = x
6        self.next = None
7
8class Solution:
9    def splitListToParts(self, root, k):
10        """
11        :type root: ListNode
12        :type k: int
13        :rtype: List[ListNode]
14        """
15        length = 0
16        curr = root
17        while curr:
18            length += 1
19            curr = curr.next
20
21        partLength, extra = divmod(length, k)
22
23        # Initialize result with k lists
24        result = [None]*k
25        curr = root
26
27        for i in range(k):
28            head = curr
29            # add an extra node for the first 'extra' parts
30            for j in range(partLength + (i < extra) - 1):
31                if curr: 
32                    curr = curr.next
33            if curr:
34                curr.next, curr = None, curr.next
35            result[i] = head
36
37        return result

In the above python solution, we first count the number of nodes in the list which is denoted by length. Then, we calculate the length of each part and number of extra nodes to the distributed using python's built-in function divmod. The python solution then iterates through the linked list and assigns a sublist to each index of result array according to the number of nodes to be distributed. The sublist with extra nodes are assigned first.

Java Solution

1
2java
3public class ListNode {
4    int val;
5    ListNode next;
6    ListNode(int x) { val = x; }
7}
8public class Solution {
9    public ListNode[] splitListToParts(ListNode root, int k) {
10        ListNode[] result = new ListNode[k];
11        int length = 0;
12        for (ListNode node = root; node != null; node = node.next)
13            length++;
14        int n = length / k, r = length % k;
15        ListNode node = root, prev = null;
16        for (int i = 0; i < k; ++i, --r) {
17            result[i] = node;
18            for (int j = 0; j < n + (i < r ? 1 : 0); ++j) {
19                prev = node;
20                node = node.next;
21            }
22            if (prev != null) 
23                prev.next = null;
24        }
25        return result;
26    }
27}

In the above Java solution, first, we compute the length of the linked list and then determine the number of nodes to be put in each section or part. We then create a new linked list for each section and populate these lists by traversing the original list.

Javascript Solution

1
2javascript
3function ListNode(val, next) {
4    this.val = (val===undefined ? 0 : val);
5    this.next = (next===undefined ? null : next);
6}
7
8var splitListToParts = function(root, k) {
9    var length = 0, curr = root;
10    while (curr != null) { curr = curr.next; length++; }
11
12    var partSize = Math.floor(length / k), extra = length % k;
13
14    var result = new Array(k).fill(null);
15    curr = root;
16
17    for (let i = 0; i < k && curr != null; i++) {
18        result[i] = curr;
19        var partSizeCurr = partSize + (i < extra ? 1 : 0);
20        for (let j = 1; j < partSizeCurr; j++) {
21            curr = curr.next;
22        }
23        var next = curr.next;
24        curr.next = null;
25        curr = next;
26    }
27    return result;
28};

In this JavaScript solution, we first compute the length of the linked list and then determine the number of nodes to be put in each section or part. result is a new array (size: k) initialized with null. We then update result by creating arrays for each part by traversing the original list.

C++ Solution

1
2c++
3class Solution {
4public:
5    vector<ListNode*> splitListToParts(ListNode* root, int k) {
6        int length = getLength(root);
7        int partLength = length / k, extra = length % k;
8        vector<ListNode*> result(k);
9        ListNode* prev = nullptr;
10        ListNode* curr = root;
11        
12        for (int i = 0; i < k && curr != nullptr; i++, --extra) {
13            result[i] = curr;
14            for (int j = 0; j < partLength + (extra > 0); ++j) {
15                prev = curr;
16                curr = curr->next;
17            }
18            prev->next = nullptr;
19        }
20        return result;
21    }
22    
23private:
24    int getLength(ListNode *node) {
25        int length = 0;
26        while(node) {
27            node = node->next;
28            length++;
29        }
30        return length;
31    }
32};

The C++ solution works similarly to the Java solution. The solution also uses a helper function named getLength( ) that computes the length of the linked list.

C# Solution

1
2c#
3public class ListNode {
4    public int val;
5    public ListNode next;
6    public ListNode(int x) { val = x; }
7}
8public class Solution {
9    public ListNode[] SplitListToParts(ListNode root, int k) {
10        var result = new ListNode[k];
11        int length = 0;
12        for (ListNode node = root; node != null; node = node.next)
13            length++;
14        int n = length / k, r = length % k;
15        ListNode node = root, prev = null;
16        for (int i = 0; i < k; ++i, --r) {
17            result[i] = node;
18            for (int j = 0; j < n + (i < r ? 1 : 0); ++j) {
19                prev = node;
20                node = node.next;
21            }
22            if (prev != null)
23                prev.next = null;
24        }
25        return result;
26    }
27}

The C# solution also works similarly to the Java solution. It computes the length of the linked list and populates the lists for each part by traversing the original list.

All the above solutions traverse the linked list once to get the length and then again k times to distribute the nodes in k groups. Hence, the time complexity of the above solutions is O(n+k) and the space complexity is O(max(n, k)) as we are storing k linked-list nodes.## Rust Solution

1
2rust
3pub struct Solution;
4pub struct ListNode {
5    pub val: i32,
6    pub next: Option<Box<ListNode>>,
7}
8
9impl Solution {
10    pub fn split_list_to_parts(root: Option<Box<ListNode>>, k: i32) -> Vec<Option<Box<ListNode>>> {
11        let mut length = 0;
12        let mut node = root.as_ref();
13        while let Some(n) = node {
14            node = n.next.as_ref();
15            length += 1;
16        }
17        let mut size = length / k;
18        let mut extra = length % k;
19    
20        let mut node = root;
21        let mut result = vec![];
22        for _ in 0..k {
23            let mut head = node;
24            let mut last = &mut head;
25            for _ in 0..size + if extra > 0 { 1 } else { 0 } {
26                extra -= 1;
27                if let Some(n) = last {
28                    last = &mut n.next;
29                }
30            }
31            if let Some(n) = last {
32                node = n.next.take();
33            }
34            result.push(head);
35        }
36        result
37    }
38}

In the above Rust solution, the linked list is also set to None after each assigned value to result, making it available for reassignment in the next iteration. It also checks to see if an extra node should be added to the current linked list by comparing the value extra to 0.

Go Solution

1
2go
3type ListNode struct {
4    Val int
5    Next *ListNode
6}
7
8func splitListToParts(root *ListNode, k int) []*ListNode {
9    length := 0
10    for node := root; node != nil; node = node.Next {
11        length++
12    }
13    partLen, extra := length/k, length%k
14    result := make([]*ListNode, k)
15    curr := root
16    for i := 0; i < k && curr != nil; i++ {
17        result[i] = curr
18        partSizeCurr := partLen
19        if i < extra {
20            partSizeCurr++
21        }
22        for j := 1; j < partSizeCurr; j++ {
23            curr = curr.next
24        }
25        curr, curr.Next = curr.Next, nil
26    }
27    return result
28}

In this Go solution, a linked list is created for each part of the original list. For the first extra parts, one additional node is added to each part to ensure the earlier parts have more nodes in the case of an uneven distribution.