Partition a Linked List into 3 parts such that the maximum difference between their sizes is minimum

0 0 11 minutes read

Given a singly linked list, the task is to split the given linked list into exactly three parts such that the maximum difference between the length of the split linked lists is minimum.

Examples:

Input: 1->2->3->4->5
Output:
1->2
3->4
5
Explanation:
Consider the splitting of the linked list as:

1->2: The size is 1.

3->4: The size is 1.

5: The size is 1.

The maximum difference between the length of any two splitted linked lists is 1, which is minimum.

Input: 7 -> 2 -> 1
Output:
7
2
1

Approach: Follow the steps below to solve the given problem:

Initialize a vector, say ans[] that stores the split linked list
If the size of the given linked list is less than 3, then create size time linked list with only one node and 3 – size linked list with null nodes and add it to the ans vector and return.
Initialize a variable, say minSize as size / 3 that will be the minimum size of the linked list to be divided and rem as size % 3.
Iterate over the linked list until size becomes 0 and perform the following steps:
- In each iteration, if rem equals 0, then iterate again minSize times into the linked list and add that linked list to the ans and decrement rem by 1.
- Otherwise, iterate (minSize + 1) a number of times into the linked list and add that linked list to the ans.
After completing the above steps, print all the Linked List stored in the vector ans[].

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a Node
class Node {
public:
    int data;
    Node* next;
};
 
// Function to find the length of
// the Linked List
int sizeOfLL(Node* head)
{
    int size = 0;
 
    // While head is not null
    while (head != NULL) {
        ++size;
        head = head->next;
    }
    return size;
}
 
// Function to partition list into
// 3 parts such that maximum size
// difference between parts is minimum
vector<Node*> Partition_of_list(Node* head)
{
    int size = sizeOfLL(head);
    Node* temp = head;
    vector<Node*> ans;
 
    // If size is less than 3
    if (3 >= size) {
        // Partition linked list
        // into one node each
        while (temp != NULL) {
            Node* next = temp->next;
            temp->next = NULL;
            ans.push_back(temp);
            temp = next;
        }
 
        // The remaining parts (3-size)
        // will be filled by empty
        // the linked list
        int y = 3 - size;
        while (y != 0) {
            ans.push_back(NULL);
            y--;
        }
    }
    else {
        // Minimum size
        int minSize = size / 3;
        int rem = size % 3;
 
        // While size is positive
        // and temp is not null
        while (size > 0 && temp != NULL) {
            int m = 0;
 
            // If remainder > 0, then
            // partition list on the
            // basis of minSize + 1
            if (rem != 0) {
                m = minSize + 1;
                rem--;
            }
 
            // Otherwise, partition
            // on the basis of minSize
            else {
                m = minSize;
            }
            Node* curr = temp;
 
            // Iterate for m-1 steps
            // in the list
            for (int j = 1; j < m
                            && temp->next != NULL;
                 j++) {
                temp = temp->next;
            }
 
            // Change the next of the
            // current node to NULL
            // and add it to the ans
            if (temp->next != NULL) {
                Node* x = temp->next;
                temp->next = NULL;
                temp = x;
                ans.push_back(curr);
            }
 
            // Otherwise
            else {
                // Pushing to ans
                ans.push_back(curr);
                break;
            }
            size -= m;
        }
    }
 
    // Return the resultant lists
    return ans;
}
 
// Function to insert elements in list
void push(Node** head, int d)
{
    Node* temp = new Node();
    temp->data = d;
    temp->next = NULL;
 
    // If the head is NULL
    if ((*head) == NULL)
        (*head) = temp;
 
    // Otherwise
    else {
        Node* curr = (*head);
 
        // While curr->next is not NULL
        while (curr->next != NULL) {
            curr = curr->next;
        }
        curr->next = temp;
    }
}
 
// Function to display the Linked list
void display(Node* head)
{
    // While head is not null
    while (head->next != NULL) {
        // Print the data
        cout << head->data << "->";
        head = head->next;
    }
    cout << head->data << "\n";
}
 
// Driver Code
int main()
{
    // Given Input
    Node* head = NULL;
    push(&head, 1);
    push(&head, 2);
    push(&head, 3);
    push(&head, 4);
    push(&head, 5);
 
    // Function Call
    vector<Node*> v = Partition_of_list(head);
 
    for (int i = 0; i < v.size(); i++) {
        display(v[i]);
    }
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Structure of a Node
static class Node {
 
    int data;Node next;
};
 
    // Function to find the length of
    // the Linked List
static int sizeOfLL(Node head)
{
    int size = 0;
 
    // While head is not null
    while (head != null) {
        ++size;
        head = head.next;
    }
    return size;
}
 
// Function to partition list into
// 3 parts such that maximum size
// difference between parts is minimum
static Vector<Node> Partition_of_list(Node head)
{
    int size = sizeOfLL(head);
    Node temp = head;
    Vector<Node> ans = new Vector<>();
 
    // If size is less than 3
    if (3 >= size) {
        // Partition linked list
        // into one node each
        while (temp != null) {
            Node next = temp.next;
            temp.next = null;
            ans.add(temp);
            temp = next;
        }
 
        // The remaining parts (3-size)
        // will be filled by empty
        // the linked list
        int y = 3 - size;
        while (y != 0) {
            ans.add(null);
            y--;
        }
    }
    else {
        // Minimum size
        int minSize = size / 3;
        int rem = size % 3;
 
        // While size is positive
        // and temp is not null
        while (size > 0 && temp != null) {
            int m = 0;
 
            // If remainder > 0, then
            // partition list on the
            // basis of minSize + 1
            if (rem != 0) {
                m = minSize + 1;
                rem--;
            }
 
            // Otherwise, partition
            // on the basis of minSize
            else {
                m = minSize;
            }
            Node curr = temp;
 
            // Iterate for m-1 steps
            // in the list
            for (int j = 1; j < m
                            && temp.next != null;
                 j++) {
                temp = temp.next;
            }
 
            // Change the next of the
            // current node to null
            // and add it to the ans
            if (temp.next != null) {
                Node x = temp.next;
                temp.next = null;
                temp = x;
                ans.add(curr);
            }
 
            // Otherwise
            else {
                // Pushing to ans
                ans.add(curr);
                break;
            }
            size -= m;
        }
    }
 
    // Return the resultant lists
    return ans;
}
 
    // Function to insert elements in list
static Node push(Node head, int d)
{
    Node temp = new Node();
    temp.data = d;
    temp.next = null;
 
    // If the head is null
    if ((head) == null)
        (head) = temp;
 
    // Otherwise
    else {
        Node curr = (head);
 
        // While curr.next is not null
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = temp;
    }
    return head;
}
 
    // Function to display the Linked list
static void display(Node head)
{
    // While head is not null
    while (head.next != null) {
        // Print the data
        System.out.print(head.data+ "->");
        head = head.next;
    }
    System.out.print(head.data+ "\n");
}
 
    // Driver Code
public static void main(String[] args)
{
    // Given Input
    Node head = null;
    head = push(head, 1);
    head = push(head, 2);
    head = push(head, 3);
    head = push(head, 4);
    head = push(head, 5);
 
    // Function Call
    Vector<Node> v = Partition_of_list(head);
 
    for (int i = 0; i < v.size(); i++) {
        display(v.get(i));
    }
}
}
// This code is contributed by gauravrajput1

Python3

# Python program for the above approach
 
# Structure of a Node
class Node: 
    def __init__(self):
        self.data = 0; 
        self.next = next;
 
# Function to find the length of
# the Linked List
def sizeOfLL(head):
    size = 0;
 
    # While head is not None
    while (head != None):
        size += 1;
        head = head.next;
     
    return size;
 
# Function to partition list into
# 3 parts such that maximum size
# difference between parts is minimum
def Partition_of_list(head):
    size = sizeOfLL(head);
    temp = head;
    ans = [];
 
    # If size is less than 3
    if (3 >= size):
       
        # Partition linked list
        # into one Node each
        while (temp != None):
            next = temp.next;
            temp.next = None;
            ans.append(temp);
            temp = next;
         
 
        # The remaining parts (3-size)
        # will be filled by empty
        # the linked list
        y = 3 - size;
        while (y != 0):
            ans.append(None);
            y-=1;
         
    else:
        # Minimum size
        minSize = size // 3;
        rem = size % 3;
 
        # While size is positive
        # and temp is not None
        while (size > 0 and temp != None):
            m = 0;
 
            # If remainder > 0, then
            # partition list on the
            # basis of minSize + 1
            if (rem != 0):
                m = minSize + 1;
                rem-=1;
             
 
            # Otherwise, partition
            # on the basis of minSize
            else:
                m = minSize;
             
            curr = temp;
 
            # Iterate for m-1 steps
            # in the list
            for j in range(1,m):# (j = 1; j < m and temp.next != None; j+=1):
                temp = temp.next;
             
 
            # Change the next of the
            # current Node to None
            # and add it to the ans
            if (temp.next != None):
                x = temp.next;
                temp.next = None;
                temp = x;
                ans.append(curr);
             
            # Otherwise
            else:
                # Pushing to ans
                ans.append(curr);
                break;
             
            size -= m;
         
    # Return the resultant lists
    return ans;
 
# Function to insert elements in list
def push(head, d):
    temp = Node();
    temp.data = d;
    temp.next = None;
 
    # If the head is None
    if ((head) == None):
        (head) = temp;
 
    # Otherwise
    else:
        curr = (head);
 
        # While curr.next is not None
        while (curr.next != None):
            curr = curr.next;
         
        curr.next = temp;
     
    return head;
 
 
# Function to display the Linked list
def display(head):
    # While head is not None
    while (head.next != None):
        # Print the data
        print(head.data , "->", end="");
        head = head.next;
     
    print(head.data );
 
# Driver Code
if __name__ == '__main__':
   
    # Given Input
    head = None;
    head = push(head, 1);
    head = push(head, 2);
    head = push(head, 3);
    head = push(head, 4);
    head = push(head, 5);
 
    # Function Call
    v = Partition_of_list(head);
 
    for i in range(len(v)):
        display(v[i]);
 
# This code is contributed by umadevi9616

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG {
 
    // Structure of a Node
public    class Node {
 
    public    int data;
    public    Node next;
    };
 
    // Function to find the length of
    // the Linked List
    static int sizeOfLL(Node head) {
        int size = 0;
 
        // While head is not null
        while (head != null) {
            ++size;
            head = head.next;
        }
        return size;
    }
 
    // Function to partition list into
    // 3 parts such that maximum size
    // difference between parts is minimum
    static List<Node> Partition_of_list(Node head) {
        int size = sizeOfLL(head);
        Node temp = head;
        List<Node> ans = new List<Node>();
 
        // If size is less than 3
        if (3 >= size) {
            // Partition linked list
            // into one node each
            while (temp != null) {
                Node next = temp.next;
                temp.next = null;
                ans.Add(temp);
                temp = next;
            }
 
            // The remaining parts (3-size)
            // will be filled by empty
            // the linked list
            int y = 3 - size;
            while (y != 0) {
                ans.Add(null);
                y--;
            }
        } else {
            // Minimum size
            int minSize = size / 3;
            int rem = size % 3;
 
            // While size is positive
            // and temp is not null
            while (size > 0 && temp != null) {
                int m = 0;
 
                // If remainder > 0, then
                // partition list on the
                // basis of minSize + 1
                if (rem != 0) {
                    m = minSize + 1;
                    rem--;
                }
 
                // Otherwise, partition
                // on the basis of minSize
                else {
                    m = minSize;
                }
                Node curr = temp;
 
                // Iterate for m-1 steps
                // in the list
                for (int j = 1; j < m && temp.next != null; j++) {
                    temp = temp.next;
                }
 
                // Change the next of the
                // current node to null
                // and add it to the ans
                if (temp.next != null) {
                    Node x = temp.next;
                    temp.next = null;
                    temp = x;
                    ans.Add(curr);
                }
 
                // Otherwise
                else {
                    // Pushing to ans
                    ans.Add(curr);
                    break;
                }
                size -= m;
            }
        }
 
        // Return the resultant lists
        return ans;
    }
 
    // Function to insert elements in list
    static Node push(Node head, int d) {
        Node temp = new Node();
        temp.data = d;
        temp.next = null;
 
        // If the head is null
        if ((head) == null)
            (head) = temp;
 
        // Otherwise
        else {
            Node curr = (head);
 
            // While curr.next is not null
            while (curr.next != null) {
                curr = curr.next;
            }
            curr.next = temp;
        }
        return head;
    }
 
    // Function to display the Linked list
    static void display(Node head) {
        // While head is not null
        while (head.next != null) {
            // Print the data
            Console.Write(head.data + "->");
            head = head.next;
        }
        Console.Write(head.data + "\n");
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
       
        // Given Input
        Node head = null;
        head = push(head, 1);
        head = push(head, 2);
        head = push(head, 3);
        head = push(head, 4);
        head = push(head, 5);
 
        // Function Call
        List<Node> v = Partition_of_list(head);
 
        for (int i = 0; i < v.Count; i++) {
            display(v[i]);
        }
    }
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
// javascript program for the above approach
 
    // Structure of a Node
     class Node {
        constructor() {
            this.data = 0;
            this.next = null;
        }
    }
 
    // Function to find the length of
    // the Linked List
    function sizeOfLL(head) {
        var size = 0;
 
        // While head is not null
        while (head != null) {
            ++size;
            head = head.next;
        }
        return size;
    }
 
    // Function to partition list into
    // 3 parts such that maximum size
    // difference between parts is minimum
     function Partition_of_list(head) {
        var size = sizeOfLL(head);
        var temp = head;
        var ans = [];
 
        // If size is less than 3
        if (3 >= size) {
            // Partition linked list
            // into one node each
            while (temp != null) {
        var next = temp.next;
                temp.next = null;
                ans.push(temp);
                temp = next;
            }
 
            // The remaining parts (3-size)
            // will be filled by empty
            // the linked list
            var y = 3 - size;
            while (y != 0) {
                ans.push(null);
                y--;
            }
        } else {
            // Minimum size
            var minSize = parseInt(size / 3);
            var rem = size % 3;
 
            // While size is positive
            // and temp is not null
            while (size > 0 && temp != null) {
                var m = 0;
 
                // If remainder > 0, then
                // partition list on the
                // basis of minSize + 1
                if (rem != 0) {
                    m = minSize + 1;
                    rem--;
                }
 
                // Otherwise, partition
                // on the basis of minSize
                else {
                    m = minSize;
                }
                var curr = temp;
 
                // Iterate for m-1 steps
                // in the list
                for (var j = 1; j < m && temp.next != null; j++) {
                    temp = temp.next;
                }
 
                // Change the next of the
                // current node to null
                // and add it to the ans
                if (temp.next != null) {
                    var x = temp.next;
                    temp.next = null;
                    temp = x;
                    ans.push(curr);
                }
 
                // Otherwise
                else {
                    // Pushing to ans
                    ans.push(curr);
                    break;
                }
                size -= m;
            }
        }
 
        // Return the resultant lists
        return ans;
    }
 
    // Function to insert elements in list
    function push(head , d) {
        var temp = new Node();
        temp.data = d;
        temp.next = null;
 
        // If the head is null
        if ((head) == null)
            (head) = temp;
 
        // Otherwise
        else {
            var curr = (head);
 
            // While curr.next is not null
            while (curr.next != null) {
                curr = curr.next;
            }
            curr.next = temp;
        }
        return head;
    }
 
    // Function to display the Linked list
    function display(head) {
        // While head is not null
        while (head.next != null) {
            // Print the data
            document.write(head.data + "->");
            head = head.next;
        }
        document.write(head.data + "<br/>");
    }
 
    // Driver Code
     
        // Given Input
        var head = null;
        head = push(head, 1);
        head = push(head, 2);
        head = push(head, 3);
        head = push(head, 4);
        head = push(head, 5);
 
        // Function Call
        var v = Partition_of_list(head);
 
        for (i = 0; i < v.length; i++) {
            display(v[i]);
        }
 
// This code is contributed by gauravrajput1 
</script>

Output:

1->2
3->4
5

Time Complexity: O(N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!