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 Nodeclass Node {public: int data; Node* next;};// Function to find the length of// the Linked Listint 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 minimumvector<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 listvoid 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 listvoid 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 Codeint 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 approachimport java.util.*;class GFG{// Structure of a Nodestatic class Node { int data;Node next;}; // Function to find the length of // the Linked Liststatic 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 minimumstatic 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 liststatic 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 liststatic 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 Codepublic 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 Nodeclass Node: def __init__(self): self.data = 0; self.next = next;# Function to find the length of# the Linked Listdef 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 minimumdef 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 listdef 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 listdef 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 Codeif __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 approachusing System;using System.Collections.Generic;public class GFG { // Structure of a Nodepublic 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
