C# || How To Split Linked List In Parts Using C#

February 01, 2025 admin No comments

The following is a module with functions which demonstrates how to split linked list in parts using C#.

1. Split Linked List In Parts – Problem Statement

Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

Example 1:

Input: head = [1,2,3], k = 5 Output: [[1],[2],[3],[],[]] Explanation: The first element output[0] has output[0].val = 1, output[0].next = null. The last element output[4] is null, but its string representation as a ListNode is [].

Example 2:

Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3 Output: [[1,2,3,4],[5,6,7],[8,9,10]] Explanation: The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

2. Split Linked List In Parts – Solution

The following is a solution which demonstrates how to split linked list in parts.





		
		
			2. Split Linked List In Parts - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Feb 1, 2025
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to split linked list in parts
// ============================================================================
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode[] SplitListToParts(ListNode head, int k) {
        // Save nodes to a list
        var items = new List<ListNode>();
        for (var iter = head; iter != null; iter = iter.next) {
            items.Add(iter);
        }

        // Create result array
        var result = new ListNode[k];

        // Determine the size of each batch
        var batchLength = (int)(items.Count / k);

        // Get the remainder
        var remainder = items.Count % k;

        var firstNodeIndex = 0;
        for (int index = 0; index < Math.Min(k, items.Count); ++index) {
            var currentBatchLength = batchLength;
            if (index < remainder) {
                currentBatchLength += 1;
            }

            var lastNodeIndex = firstNodeIndex + (currentBatchLength - 1);

            // Get the head and tail nodes for this batch
            var batchHead = items[firstNodeIndex];
            var batchTail = items[lastNodeIndex];

            // Set the tail to null
            batchTail.next = null;

            // Save the head to the result array
            result[index] = batchHead;

            // Increment the first node index
            firstNodeIndex = lastNodeIndex + 1;
        }

        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Feb 1, 2025
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to split linked list in parts
// ============================================================================
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode[] SplitListToParts(ListNode head, int k) {
        // Save nodes to a list
        var items = new List<ListNode>();
        for (var iter = head; iter != null; iter = iter.next) {
            items.Add(iter);
        }
 
        // Create result array
        var result = new ListNode[k];
 
        // Determine the size of each batch
        var batchLength = (int)(items.Count / k);
 
        // Get the remainder
        var remainder = items.Count % k;
 
        var firstNodeIndex = 0;
        for (int index = 0; index < Math.Min(k, items.Count); ++index) {
            var currentBatchLength = batchLength;
            if (index < remainder) {
                currentBatchLength += 1;
            }
 
            var lastNodeIndex = firstNodeIndex + (currentBatchLength - 1);
 
            // Get the head and tail nodes for this batch
            var batchHead = items[firstNodeIndex];
            var batchTail = items[lastNodeIndex];
 
            // Set the tail to null
            batchTail.next = null;
 
            // Save the head to the result array
            result[index] = batchHead;
 
            // Increment the first node index
            firstNodeIndex = lastNodeIndex + 1;
        }
 
        return result;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[[1],[2],[3],[],[]] [[1,2,3,4],[5,6,7],[8,9,10]]

Was this article helpful?

👍 YesNo

Posted in: C#, Console Tags: c-sharp, leetcode, linked list

C# || How To Split Linked List In Parts Using C#

Related

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories