Dada una lista enlazada individualmente y un entero K , la tarea es eliminar todo el conjunto continuo de Nodes cuya suma es K de la lista enlazada dada . Imprima la lista vinculada actualizada después de la eliminación. Si no puede ocurrir tal eliminación, imprima la lista Vinculada original.
Ejemplos:
Entrada: Lista enlazada: 1 -> 2 -> -3 -> 3 -> 1, K = 3
Salida: -3 -> 1
Explicación:
Los Nodes con suma continua 3 son:
1) 1 -> 2
2) 3
Por lo tanto, después de eliminar esta string de Nodes, la Lista enlazada se convierte en: -3-> 1
Entrada: Lista enlazada: 1 -> 1 -> -3 -> -3 -> -2, K = 5
Salida: 1 -> 1 -> -3 -> -3 -> -2
Explicación:
No salen Nodes continuos con suma K
Acercarse:
- Agregar Node con valor cero al comienzo de la lista vinculada.
- Atraviesa la lista enlazada dada .
- Durante el recorrido, almacene la suma del valor del Node hasta ese Node con la referencia del Node actual en un mapa_desordenado .
- Si hay un Node con valor (suma – K) presente en unordered_map , elimine todos los Nodes del Node correspondiente al valor (suma – K) almacenado en el mapa del Node actual y actualice la suma como (suma – K) .
- Si no hay ningún Node con valor (suma – K) presente en unordered_map, almacene la suma actual con el Node en el mapa.
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;
// A Linked List Node
struct ListNode {
int val;
ListNode* next;
// Constructor
ListNode(int x)
: val(x)
, next(NULL)
{
}
};
// Function to create Node
ListNode* getNode(int data)
{
ListNode* temp;
temp = (ListNode*)malloc(sizeof(ListNode));
temp->val = data;
temp->next = NULL;
return temp;
}
// Function to print the Linked List
void printList(ListNode* head)
{
while (head->next) {
cout << head->val << " -> ";
head = head->next;
}
printf("%d", head->val);
}
// Function that removes continuous nodes
// whose sum is K
ListNode* removeZeroSum(ListNode* head, int K)
{
// Root node initialise to 0
ListNode* root = new ListNode(0);
// Append at the front of the given
// Linked List
root->next = head;
// Map to store the sum and reference
// of the Node
unordered_map<int, ListNode*> umap;
umap[0] = root;
// To store the sum while traversing
int sum = 0;
// Traversing the Linked List
while (head != NULL) {
// Find sum
sum += head->val;
// If found value with (sum - K)
if (umap.find(sum - K) != umap.end()) {
ListNode* prev = umap[sum - K];
ListNode* start = prev;
// Update sum
sum = sum - K;
int aux = sum;
// Traverse till current head
while (prev != head) {
prev = prev->next;
aux += prev->val;
if (prev != head) {
umap.erase(aux);
}
}
// Update the start value to
// the next value of current head
start->next = head->next;
}
// If (sum - K) value not found
else if (umap.find(sum) == umap.end()) {
umap[sum] = head;
}
head = head->next;
}
// Return the value of updated
// head node
return root->next;
}
// Driver Code
int main()
{
// head Node
ListNode* head;
// Create Linked List
head = getNode(1);
head->next = getNode(2);
head->next->next = getNode(-3);
head->next->next->next = getNode(3);
head->next->next->next->next = getNode(1);
// Given sum K
int K = 5;
// Function call to get head node
// of the updated Linked List
head = removeZeroSum(head, K);
// Print the updated Linked List
if (head != NULL)
printList(head);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
// A Linked List Node
class ListNode {
int val;
ListNode next;
// Constructor
ListNode(int val)
{
this.val = val;
this.next = null;
}
}
class GFG {
// Function to create Node
static ListNode getNode(int data)
{
ListNode temp = new ListNode(data);
return temp;
}
// Function to print the Linked List
static void printList(ListNode head)
{
while (head.next != null) {
System.out.print(head.val + " -> ");
head = head.next;
}
System.out.print(head.val);
}
// Function that removes continuous nodes
// whose sum is K
static ListNode removeZeroSum(ListNode head, int K)
{
// Root node initialise to 0
ListNode root = new ListNode(0);
// Append at the front of the given
// Linked List
root.next = head;
// Map to store the sum and reference
// of the Node
Map<Integer, ListNode> umap
= new HashMap<Integer, ListNode>();
umap.put(0, root);
// To store the sum while traversing
int sum = 0;
// Traversing the Linked List
while (head != null) {
// Find sum
sum += head.val;
// If found value with (sum - K)
if (umap.containsKey(sum - K)) {
ListNode prev = umap.get(sum - K);
ListNode start = prev;
// Delete all the node
// traverse till current node
int aux = sum;
// Update sum
sum = sum - K;
// Traverse till current head
while (prev != head) {
prev = prev.next;
aux += prev.val;
if (prev != head) {
umap.remove(aux);
}
}
// Update the start value to
// the next value of current head
start.next = head.next;
}
// If (sum - K) value not found
else if (!umap.containsKey(sum)) {
umap.put(sum, head);
}
head = head.next;
}
// Return the value of updated
// head node
return root.next;
}
// Driver code
public static void main(String[] args)
{
// head Node
ListNode head;
// Create Linked List
head = getNode(1);
head.next = getNode(2);
head.next.next = getNode(-3);
head.next.next.next = getNode(3);
head.next.next.next.next = getNode(1);
// Given sum K
int K = 5;
// Function call to get head node
// of the updated Linked List
head = removeZeroSum(head, K);
// Print the updated Linked List
if (head != null)
printList(head);
}
}
// This code is contributed by jitin.
Python3
# Python3 program for the above approach # A Linked List Node class ListNode: def __init__(self, val): self.val = val self.next = None # Function to create Node def getNode(data): temp = ListNode(data) temp.next = None return temp # Function to print the Linked List def printList(head): while (head.next): print(head.val, end=' -> ') head = head.next print(head.val, end='') # Function that removes continuous nodes # whose sum is K def removeZeroSum(head, K): # Root node initialise to 0 root = ListNode(0) # Append at the front of the given # Linked List root.next = head # Map to store the sum and reference # of the Node umap = dict() umap[0] = root # To store the sum while traversing sum = 0 # Traversing the Linked List while (head != None): # Find sum sum += head.val # If found value with (sum - K) if ((sum - K) in umap): prev = umap[sum - K] start = prev # Delete all the node # traverse till current node aux = sum # Update sum sum = sum - K # Traverse till current head while (prev != head): prev = prev.next aux += prev.val if (prev != head): umap.remove(aux) # Update the start value to # the next value of current head start.next = head.next # If (sum - K) value not found else: umap[sum] = head head = head.next # Return the value of updated # head node return root.next # Driver Code if __name__ == '__main__': # Create Linked List head = getNode(1) head.next = getNode(2) head.next.next = getNode(-3) head.next.next.next = getNode(3) head.next.next.next.next = getNode(1) # Given sum K K = 5 # Function call to get head node # of the updated Linked List head = removeZeroSum(head, K) # Print the updated Linked List if(head != None): printList(head) # This code is contributed by pratham76
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
// A Linked List Node
class ListNode {
public int val;
public ListNode next;
// Constructor
public ListNode(int val)
{
this.val = val;
this.next = null;
}
}
class GFG {
// Function to create Node
static ListNode getNode(int data)
{
ListNode temp = new ListNode(data);
return temp;
}
// Function to print the Linked List
static void printList(ListNode head)
{
while (head.next != null) {
Console.Write(head.val + " -> ");
head = head.next;
}
Console.Write(head.val);
}
// Function that removes continuous nodes
// whose sum is K
static ListNode removeZeroSum(ListNode head, int K)
{
// Root node initialise to 0
ListNode root = new ListNode(0);
// Append at the front of the given
// Linked List
root.next = head;
// Map to store the sum and reference
// of the Node
Dictionary<int, ListNode> umap
= new Dictionary<int, ListNode>();
umap.Add(0, root);
// To store the sum while traversing
int sum = 0;
// Traversing the Linked List
while (head != null) {
// Find sum
sum += head.val;
// If found value with (sum - K)
if (umap.ContainsKey(sum - K)) {
ListNode prev = umap[sum - K];
ListNode start = prev;
// Delete all the node
// traverse till current node
int aux = sum;
// Update sum
sum = sum - K;
// Traverse till current head
while (prev != head) {
prev = prev.next;
aux += prev.val;
if (prev != head) {
umap.Remove(aux);
}
}
// Update the start value to
// the next value of current head
start.next = head.next;
}
// If (sum - K) value not found
else if (!umap.ContainsKey(sum)) {
umap.Add(sum, head);
}
head = head.next;
}
// Return the value of updated
// head node
return root.next;
}
// Driver code
public static void Main(string[] args)
{
// head Node
ListNode head;
// Create Linked List
head = getNode(1);
head.next = getNode(2);
head.next.next = getNode(-3);
head.next.next.next = getNode(3);
head.next.next.next.next = getNode(1);
// Given sum K
int K = 5;
// Function call to get head node
// of the updated Linked List
head = removeZeroSum(head, K);
// Print the updated Linked List
if (head != null)
printList(head);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript program for the above approach
// A Linked List Node
class ListNode{
constructor(val){
this.val = val
this.next = null
}
}
// Function to create Node
function getNode(data){
let temp = new ListNode(data)
temp.next = null
return temp
}
// Function to print the Linked List
function printList(head){
while (head.next){
document.write(head.val,' -> ')
head = head.next
}
document.write(head.val,'')
}
// Function that removes continuous nodes
// whose sum is K
function removeZeroSum(head, K){
// Root node initialise to 0
let root = new ListNode(0)
// Append at the front of the given
// Linked List
root.next = head
// Map to store the sum and reference
// of the Node
let umap = new Map();
umap.set(0,root)
// To store the sum while traversing
let sum = 0
// Traversing the Linked List
while (head != null){
// Find sum
sum += head.val
// If found value with (sum - K)
if (umap.has(sum - K) == true){
let prev = umap.get(sum - K)
let start = prev
// Delete all the node
// traverse till current node
let aux = sum
// Update sum
sum = sum - K
// Traverse till current head
while (prev != head){
prev = prev.next
aux += prev.val
if (prev != head)
umap.delete(aux)
}
// Update the start value to
// the next value of current head
start.next = head.next
}
// If (sum - K) value not found
else
umap.set(sum,head)
head = head.next
}
// Return the value of updated
// head node
return root.next
}
// Driver Code
// Create Linked List
let head = getNode(1)
head.next = getNode(2)
head.next.next = getNode(-3)
head.next.next.next = getNode(3)
head.next.next.next.next = getNode(1)
// Given sum K
let K = 5
// Function call to get head node
// of the updated Linked List
head = removeZeroSum(head, K)
// Print the updated Linked List
if(head != null)
printList(head)
// This code is contributed by shinjanpatra
</script>
Producción
1 -> 2 -> -3 -> 3 -> 1
Complejidad de tiempo: O(N) , donde N es el número de Nodes en la lista enlazada.
Complejidad del Espacio Auxiliar: O(N) , donde N es el número de Node en la Lista Enlazada.