Dada una lista enlazada individualmente , la tarea es dividir la lista enlazada dada en exactamente tres partes, de modo que la diferencia máxima entre la longitud de las listas enlazadas divididas sea mínima.
Ejemplos:
Entrada: 1->2->3->4->5
Salida:
1->2
3->4
5
Explicación:
Considere la división de la lista enlazada como:
- 1->2: El tamaño es 1.
- 3->4: El tamaño es 1.
- 5: El tamaño es 1.
La diferencia máxima entre la longitud de dos listas enlazadas divididas es 1, que es el mínimo.
Entrada: 7 -> 2 -> 1
Salida:
7
2
1
Enfoque: siga los pasos a continuación para resolver el problema dado:
- Inicialice un vector , digamos ans[] que almacena la lista dividida enlazada
- Si el tamaño de la lista vinculada dada es inferior a 3 , cree una lista vinculada de tamaño y tiempo con un solo Node y una lista vinculada de 3 tamaños con Nodes nulos y agréguela al vector ans y regrese .
- Inicialice una variable, diga minSize como tamaño / 3 que será el tamaño mínimo de la lista vinculada que se dividirá y rem como tamaño % 3 .
- Iterar sobre la lista enlazada hasta que el tamaño sea 0 y realizar los siguientes pasos:
- En cada iteración, si rem es igual a 0 , vuelva a iterar minSize veces en la lista vinculada y agregue esa lista vinculada a ans y disminuya rem en 1.
- De lo contrario, itere (minSize + 1) varias veces en la lista vinculada y agregue esa lista vinculada a ans .
- Después de completar los pasos anteriores, imprima toda la lista enlazada almacenada en el vector ans[] .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
1->2 3->4 5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por prathamjha5683 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA