Dada una lista enlazada que consta de N Nodes y un número entero K , la tarea es dividir la lista enlazada dada en K grupos continuos de modo que la diferencia entre el tamaño de los grupos adyacentes después de la división sea como máximo 1 y los grupos se ordenen de forma descendente orden de sus longitudes.
Nota : También se puede formar un grupo con 0 elementos.
Ejemplos:
Entrada: 1 → 2 → 3 → 4, K = 5
Salida: {{1}, {2}, {3}, {4}, {}}
Explicación: las divisiones requeridas son {{1 -> NULL}, {2 -> NULO}, {3 -> NULO}, {4 -> NULO}, {NULO}}.Entrada: LL: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8, K = 3
Salida: {{1, 2, 3}, {4, 5, 6}, {7, 8}}
Enfoque: El problema dado se puede resolver basándose en la observación de que la formación de los primeros N % K grupos de tamaño (N / K + 1) y los restantes K – (N % K) grupos de tamaño N / K satisface las condiciones. Siga los pasos a continuación para resolver el problema:
- Inicializa un vector de la lista enlazada , dice ans , que almacena los K grupos.
- Almacene el valor de N / K y N % K en las variables, digamos L y R .
- Recorra la lista enlazada dada y realice los siguientes pasos:
- Almacene el valor de L en una variable, digamos X , y el valor de head en la variable, digamos currHead y last .
- Si el valor de R es positivo, actualice el valor de head to head->next .
- Iterar un bucle hasta que X sea distinto de cero y realizar los siguientes pasos:
- Si el último Node es el mismo que el Node principal , mueva el Node principal al siguiente Node.
- De lo contrario, una los enlaces entre el último Node y el Node principal y actualice el último a la cabecera, y mueva el Node principal al siguiente Node.
- Empuje la lista enlazada actual como currentHead en el vector ans[] .
- Si el valor de K es mayor que 0 , empuje la lista enlazada NULL en respuesta y disminuya K en 1.
- Después de completar los pasos anteriores, imprima los elementos de 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;
// Link List Node
struct ListNode {
int val;
struct ListNode* next;
};
// Function to insert a node
// into the Linked List
void push(ListNode** head_ref,
int node_val)
{
// Allocate a new dynamic node
ListNode* new_node = new ListNode();
// Update new_node->val
new_node->val = node_val;
// Stores the head_ref
new_node->next = (*head_ref);
// Update (*head_ref)
(*head_ref) = new_node;
}
// Function to split the linked list
// in K groups
void splitListInParts(ListNode* head,
int K)
{
// Stores the K groups
vector<ListNode*> ans;
// If head is NULL
if (!head) {
// Iterate until K is non-zero
while (K--)
ans.push_back(NULL);
}
// Stores the length of the
// linked list
int N = 0;
// Stores the head node of the
// linked list
ListNode* p = head;
// Iterate over the linked list
while (p) {
// Update p
p = p->next;
// Update N
N++;
}
int len = N / K;
int rem = N % K;
p = head;
// Iterate over the linked list
while (K > 0 && p) {
// Stores the length
// of the current group
int x = len;
// Stores the current node
ListNode* curr_head = p;
// Stores the previous node
ListNode* last = p;
// If rem is greater than 0
if (rem > 0) {
// Update p
p = p->next;
// Decrement rem by 1
rem--;
}
// Iterate until x is non-zero
while (x--) {
// If the last is equal to p
if (last == p)
p = p->next;
// Otherwise
else {
// Join the link between
// last and the current
// element
last->next = p;
// Update the last node
last = p;
// Update p node
p = p->next;
}
}
// Assign NULL to last->next
last->next = NULL;
// Push the current linked
// list in ans
ans.push_back(curr_head);
// Decrement K
K--;
}
// While K greater than 0
while (K > 0) {
// Update the value of ans
ans.push_back(NULL);
// Increment K
K--;
}
// Print the result
cout << "{";
for (int i = 0; i < ans.size(); i++) {
cout << "{";
while (ans[i]) {
// Print the value
cout << ans[i]->val << " ";
// Update ans[i]
ans[i] = ans[i]->next;
}
cout << "}";
if (i != ans.size() - 1)
cout << ", ";
}
cout << "}";
}
// Driver Code
int main()
{
ListNode* root = NULL;
push(&root, 8);
push(&root, 7);
push(&root, 6);
push(&root, 5);
push(&root, 4);
push(&root, 3);
push(&root, 2);
push(&root, 1);
int K = 3;
splitListInParts(root, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Link List Node
static class ListNode
{
int val;
ListNode next;
};
// Function to insert a node
// into the Linked List
static ListNode push(ListNode head_ref,
int node_val)
{
// Allocate a new dynamic node
ListNode new_node = new ListNode();
// Update new_node.val
new_node.val = node_val;
// Stores the head_ref
new_node.next = head_ref;
// Update head_ref
head_ref = new_node;
return head_ref;
}
// Function to split the linked list
// in K groups
static void splitListInParts(ListNode head,
int K)
{
// Stores the K groups
Vector<ListNode> ans = new Vector<ListNode>();
// If head is null
if (head == null)
{
// Iterate until K is non-zero
while (K-- > 0)
ans.add(null);
}
// Stores the length of the
// linked list
int N = 0;
// Stores the head node of the
// linked list
ListNode p = head;
// Iterate over the linked list
while (p.next != null)
{
// Update p
p = p.next;
// Update N
N++;
}
int len = N / K;
int rem = N % K;
p = head;
// Iterate over the linked list
while (K > 0 && p.next != null)
{
// Stores the length
// of the current group
int x = len;
// Stores the current node
ListNode curr_head = p;
// Stores the previous node
ListNode last = p;
// If rem is greater than 0
if (rem > 0)
{
// Update p
p = p.next;
// Decrement rem by 1
rem--;
}
// Iterate until x is non-zero
while (x-- > 0)
{
// If the last is equal to p
if (last == p)
p = p.next;
// Otherwise
else
{
// Join the link between
// last and the current
// element
last.next = p;
// Update the last node
last = p;
// Update p node
p = p.next;
}
}
// Assign null to last.next
last.next = null;
// Push the current linked
// list in ans
ans.add(curr_head);
// Decrement K
K--;
}
// While K greater than 0
while (K > 0)
{
// Update the value of ans
ans.add(null);
// Increment K
K--;
}
// Print the result
System.out.print("{");
for(int i = 0; i < ans.size(); i++)
{
System.out.print("{");
while (ans.get(i) != null)
{
// Print the value
System.out.print(ans.get(i).val + " ");
// Update ans[i]
ans.set(i, ans.get(i).next);
}
System.out.print("}");
if (i != ans.size() - 1)
System.out.print(", ");
}
System.out.print("}");
}
// Driver Code
public static void main(String[] args)
{
ListNode root = new ListNode();
root = push(root, 8);
root = push(root, 7);
root = push(root, 6);
root = push(root, 5);
root = push(root, 4);
root = push(root, 3);
root = push(root, 2);
root = push(root, 1);
int K = 3;
splitListInParts(root, K);
}
}
// This code is contributed by shikhasingrajput
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Link List Node
class ListNode
{
public int val;
public ListNode next;
};
// Function to insert a node
// into the Linked List
static ListNode push(ListNode head_ref,
int node_val)
{
// Allocate a new dynamic node
ListNode new_node = new ListNode();
// Update new_node.val
new_node.val = node_val;
// Stores the head_ref
new_node.next = head_ref;
// Update head_ref
head_ref = new_node;
return head_ref;
}
// Function to split the linked list
// in K groups
static void splitListInParts(ListNode head,
int K)
{
// Stores the K groups
List<ListNode> ans = new List<ListNode>();
// If head is null
if (head == null)
{
// Iterate until K is non-zero
while (K-- > 0)
ans.Add(null);
}
// Stores the length of the
// linked list
int N = 0;
// Stores the head node of the
// linked list
ListNode p = head;
// Iterate over the linked list
while (p.next != null)
{
// Update p
p = p.next;
// Update N
N++;
}
int len = N / K;
int rem = N % K;
p = head;
// Iterate over the linked list
while (K > 0 && p.next != null)
{
// Stores the length
// of the current group
int x = len;
// Stores the current node
ListNode curr_head = p;
// Stores the previous node
ListNode last = p;
// If rem is greater than 0
if (rem > 0)
{
// Update p
p = p.next;
// Decrement rem by 1
rem--;
}
// Iterate until x is non-zero
while (x-- > 0)
{
// If the last is equal to p
if (last == p)
p = p.next;
// Otherwise
else
{
// Join the link between
// last and the current
// element
last.next = p;
// Update the last node
last = p;
// Update p node
p = p.next;
}
}
// Assign null to last.next
last.next = null;
// Push the current linked
// list in ans
ans.Add(curr_head);
// Decrement K
K--;
}
// While K greater than 0
while (K > 0)
{
// Update the value of ans
ans.Add(null);
// Increment K
K--;
}
// Print the result
Console.Write("{");
for(int i = 0; i < ans.Count; i++)
{
Console.Write("{");
while (ans[i] != null)
{
// Print the value
Console.Write(ans[i].val + " ");
// Update ans[i]
ans[i] = ans[i].next;
}
Console.Write("}");
if (i != ans.Count - 1)
Console.Write(", ");
}
Console.Write("}");
}
// Driver Code
public static void Main(String[] args)
{
ListNode root = new ListNode();
root = push(root, 8);
root = push(root, 7);
root = push(root, 6);
root = push(root, 5);
root = push(root, 4);
root = push(root, 3);
root = push(root, 2);
root = push(root, 1);
int K = 3;
splitListInParts(root, K);
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// javascript program for the above approach
// Link List Node
class ListNode {
constructor()
{
this.val = 0;
this.next = null;
}
};
// Function to insert a node
// into the Linked List
function pushIn(head_ref, node_val)
{
// Allocate a new dynamic node
var new_node = new ListNode();
// Update new_node.val
new_node.val = node_val;
// Stores the head_ref
new_node.next = (head_ref);
// Update (*head_ref)
head_ref = new_node;
return head_ref;
}
// Function to split the linked list
// in K groups
function splitListInParts(head, K)
{
// Stores the K groups
var ans = [];
// If head is null
if (!head) {
// Iterate until K is non-zero
while (K--)
ans.push(null);
}
// Stores the length of the
// linked list
var N = 0;
// Stores the head node of the
// linked list
var p = head;
// Iterate over the linked list
while (p) {
// Update p
p = p.next;
// Update N
N++;
}
var len = parseInt(N / K);
var rem = N % K;
p = head;
// Iterate over the linked list
while (K > 0 && p) {
// Stores the length
// of the current group
var x = len;
// Stores the current node
var curr_head = p;
// Stores the previous node
var last = p;
// If rem is greater than 0
if (rem > 0) {
// Update p
p = p.next;
// Decrement rem by 1
rem--;
}
// Iterate until x is non-zero
while (x--) {
// If the last is equal to p
if (last == p)
p = p.next;
// Otherwise
else {
// Join the link between
// last and the current
// element
last.next = p;
// Update the last node
last = p;
// Update p node
p = p.next;
}
}
// Assign null to last.next
last.next = null;
// Push the current linked
// list in ans
ans.push(curr_head);
// Decrement K
K--;
}
// While K greater than 0
while (K > 0) {
// Update the value of ans
ans.push(null);
// Increment K
K--;
}
// Print the result
document.write( "{");
for (var i = 0; i < ans.length; i++) {
document.write( "{");
while (ans[i]) {
// Print the value
document.write( ans[i].val + " ");
// Update ans[i]
ans[i] = ans[i].next;
}
document.write( "}");
if (i != ans.length - 1)
document.write( ", ");
}
document.write( "}");
}
// Driver Code
var root = null;
root = pushIn(root, 8);
root = pushIn(root, 7);
root = pushIn(root, 6);
root = pushIn(root, 5);
root = pushIn(root, 4);
root = pushIn(root, 3);
root = pushIn(root, 2);
root = pushIn(root, 1);
var K = 3;
splitListInParts(root, K);
// This code is contributed by rrrtnx.
</script>
Producción:
{{1 2 3 }, {4 5 6 }, {7 8 }}
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rahulagarwal14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA