6

Partition a Linked List into 3 parts such that the maximum difference between th...

 2 years ago
source link: https://www.geeksforgeeks.org/partition-a-linked-list-into-3-parts-such-that-the-maximum-difference-between-their-sizes-is-minimum/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

  • Last Updated : 09 Mar, 2022

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. 1->2: The size is 1.
  2. 3->4: The size is 1.
  3. 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 timelinked 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:

  • Python3
  • Javascript
// 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;
}
Output: 
1->2
3->4
5

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

2022-05-27-10-45-13-image-(1).png

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK