Minimice el primer Node de la lista vinculada eliminándolo primero o agregando un Node eliminado al inicio

Dada una lista enlazada individualmente y un número entero K , la tarea es hacer que el valor del primer Node sea el mínimo posible en K operaciones, donde en cada operación:

• Seleccione el primer Node de la lista vinculada y elimínelo.
• Agregue un Node eliminado anteriormente al comienzo de la lista vinculada.

Ejemplos:

Entrada: lista: 1->4->2->5->3, K=4 
Salida: 1
Explicación: 
1.ª operación-> Quitar el 1.er Node, después de realizar la operación, la lista vinculada se convierte en 4->2->5->3
2.ª operación-> Eliminar el 1.er Node. Después de realizar la operación, la lista vinculada se convierte en 2->5->3
3.ª operación-> Eliminar el 1.er Node. Después de realizar la operación, la lista vinculada se convierte en 5->3
4.ª operación-> Agregar el Node previamente eliminado (es decir, 1 ), Después de realizar la operación, la lista enlazada se convierte en 1->5->3

Entrada: Lista enlazada: 5, K = 1
Salida: -1
Explicación: La única operación posible es eliminar el primer Node.
Si se realiza esa operación, la lista estará vacía.

Enfoque: el problema se puede resolver utilizando la siguiente observación:

En primeras operaciones K- 1 , se puede quitar el valor K-1 del arranque . Así que actualmente en el Node Kth. Ahora en la última operación hay dos opciones posibles:

• Quite el Node inicial actual (óptimo si el valor del Node (K+1) es más pequeño que el más pequeño entre los primeros elementos K-1 ya eliminados)
• Agregue el más pequeño de los elementos K-1 ya eliminados (óptimo cuando el Node (K+1)th tiene un valor más alto que el más pequeño)

Siga los pasos a continuación para resolver el problema:

• Si K = 0 , devuelva el valor del primer Node.
• Si K = 1 , devuelve el valor del segundo Node (si lo hay), de lo contrario, devuelve -1 (porque después de K operaciones, la lista no existe).
• Si el tamaño de la lista enlazada es uno, entonces en cada operación impar (es decir, 1, 3, 5, . . . ), devuelve -1, de lo contrario, devuelve el valor del primer Node (por la misma razón anterior).
• Si K > 2 , entonces:
  • Atraviese los primeros Nodes K-1 y descubra el valor mínimo.
  • Compare ese valor mínimo con el valor del Node (K+1) .
  • Si el valor (K+1)th es menor que el valor mínimo anterior, actualícelo con el valor del Node (K+1)th .
• Devuelve el valor mínimo. 

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of node of singly linked list
struct Node {
    int data;
    Node* next;
    Node(int x)
    {
        data = x;
        next = NULL;
    }
};
 
// Inserting new node
// at the  beginning of the linked list
void push(struct Node** head_ref,
          int new_data)
{
    // Create a new node with the given data.
    struct Node* new_node = new Node(new_data);
 
    // Make the new node point to the head.
    new_node->next = (*head_ref);
 
    // Make the new node as the head node.
    (*head_ref) = new_node;
}
 
// Function to find the
// minimum possible first node
int FirstNode(Node* head, int K)
{
    if (K == 0) {
        return head->data;
    }
    if (K == 1) {
        return (head->next == NULL) ? -1 : head->next->data;
    }
    if (head->next == NULL) {
        return (K % 2) ? -1 : head->data;
    }
    int ans = INT_MAX;
    int i = 0;
 
    // Traverse 1st K-1 Nodes and find out
    // minimum node
    // value
    while (head != NULL && i < K - 1) {
        if (head->data < ans)
            ans = head->data;
        head = head->next;
        i++;
    }
 
    // Check whether Linked list have (K+1)th
    // Node or not
    if (head && head->next != NULL) {
 
        // Update ans with minimum of 1st K-1
        // nodes and the (K+1)th Node.
        ans = min(ans, head->next->data);
    }
    return ans;
}
 
// Driver code
int main()
{
    int K = 4;
 
    // Create an empty singly linked list
    struct Node* head = NULL;
 
    // Insert values in Linked List
    push(&head, 3);
    push(&head, 5);
    push(&head, 2);
    push(&head, 4);
    push(&head, 1);
 
    // Call FirstNode function
    cout << FirstNode(head, K);
    return 0;
}

// Java Program for the above approach
 
import java.io.*;
 
class GFG {
 
      // structure of a node.
    class Node {
        int data;
        Node next;
        Node(int data)
        {
            this.data = data;
            this.next = null;
        }
    }
     
      // Creating a head node.
      Node head;
       
      // Inserting nodes into linked list.
    public void push(int data)
    {
        Node new_node = new Node(data);
        new_node.next = head;
        head = new_node;
    }
 
      // Method to find the minumum possible time.
    public int firstNode(int k)
    {
        int ans = Integer.MAX_VALUE;
        int i = 0;
        if (k == 0) {
            return head.data;
        }
        if (k == 1) {
            return (head.next == null) ? -1
                                       : head.next.data;
        }
        if (head.next == null) {
            if (k % 2 == 1) {
                return -1;
            }
            return head.data;
        }
 
        while (head != null && (i < k - 1)) {
            if (head.data < ans) {
                ans = head.data;
            }
            head = head.next;
            i++;
        }
        if (head != null && head.next != null) {
            ans = Math.min(ans, head.next.data);
        }
        return ans;
    }
 
    public static void main(String[] args)
    {
        GFG list = new GFG();
 
          // Insert values in linked list.
        list.push(3);
        list.push(5);
        list.push(2);
        list.push(4);
        list.push(1);
 
        int k = 4;
        System.out.print(list.firstNode(k));
    }
}
 
// This code is contributed by lokesh (lokeshmvs21).

# Python code for the above approach
 
# Node Class
class Node:
    def __init__(self, d):
        self.data = d
        self.next = None
             
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    ## Inserting new node
    ## at the beginning of the linked list
    def push(self, new_data):
 
        ## Create a new node with the given data.
        new_node = Node(new_data)
 
        ## Make the new node point to the head.
        new_node.next = self.head
 
        ## Make the new node as the head node.
        self.head = new_node
 
    ## Function to find the
    ## minimum possible first node
    def FirstNode(self, K):
        if(K == 0):
            return self.head.data
        elif (K == 1):
            if (self.head.next == None):
                return -1
            return  self.head.next.data
        elif (self.head.next == None):
            if(K%2==1):
                return -1
            return self.head.data
        ## Initialize answer with Ininity
        ans = 1000000000000000000
        i = 0
 
        ## Traverse 1st K-1 nodes and find out
        ## minimum node value
        while(self.head != None and i < (K-1)):
            if(self.head.data < ans):
                ans = self.head.data
            self.head = self.head.next
            i+=1
         
        ## Check whether Linked list have (K+1)th
        ## Node or not
        if(self.head != None and self.head.next != None):
 
            ## Update ans with minimum of 1st K-1
            ## nodes and the (K+1)th Node.
            ans = min(ans, self.head.next.data)
         
        return ans
 
 
# Driver Code
if __name__=='__main__':
 
    K = 4
 
    ## Create an empty singly linked list
    llist = LinkedList()
 
    llist.push(3)
    llist.push(5)
    llist.push(2)
    llist.push(4)
    llist.push(1)
 
    ## Call FirstNode function
    print(llist.FirstNode(K))
 
    # This code is contributed by subhamgoyal2014.

// C# program for the above approach
using System;
 
public class GFG {
 
    // Structure of a node.
    class Node {
        public int data;
        public Node next;
        public Node(int data)
        {
            this.data = data;
            this.next = null;
        }
    }
 
    // Creating a head node.
    Node head;
 
    // Inserting nodes into linked list.
    public void push(int data)
    {
        Node new_node = new Node(data);
        new_node.next = head;
        head = new_node;
    }
 
    // Function to find the minimum possible time.
    public int firstNode(int k)
    {
        int ans = Int32.MaxValue;
        int i = 0;
        if (k == 0) {
            return head.data;
        }
        if (k == 1) {
            return (head.next == null) ? -1
                                       : head.next.data;
        }
        if (head.next == null) {
            if (k % 2 == 1) {
                return -1;
            }
            return head.data;
        }
        while (head != null && (i < k - 1)) {
            if (head.data < ans) {
                ans = head.data;
            }
            head = head.next;
            i++;
        }
        if (head != null && head.next != null) {
            ans = Math.Min(ans, head.next.data);
        }
        return ans;
    }
 
    static public void Main()
    {
 
        // Code
        GFG list = new GFG();
 
        // Insert values in linked list.
        list.push(3);
        list.push(5);
        list.push(2);
        list.push(4);
        list.push(1);
 
        int k = 4;
        Console.WriteLine(list.firstNode(k));
    }
}
 
// This code is contributed by lokesh (lokeshmvs21).

<script>
 
// JavaScript code for the above approach
 
// Node Class
class Node{
    constructor(d){
        this.data = d
        this.next = null
    }
}
             
class LinkedList{
    constructor(){
        this.head = null
    }
 
    // Inserting new node
    // at the beginning of the linked list
    push(new_data){
 
        // Create a new node with the given data.
        let new_node = new Node(new_data)
 
        // Make the new node point to the head.
        new_node.next = this.head
 
        // Make the new node as the head node.
        this.head = new_node
    }
 
    // function to find the
    // minimum possible first node
    FirstNode(K){
        if(K == 0)
            return this.head.data
        else if (K == 1){
            if (this.head.next == null)
                return -1
            return  this.head.next.data
        }
        else if (this.head.next == null){
            if(K%2==1)
                return -1
            return this.head.data
        }
        // Initialize answer with Ininity
        let ans = 1000000000000000000
        let i = 0
 
        // Traverse 1st K-1 nodes and find out
        // minimum node value
        while(this.head != null && i < (K-1)){
            if(this.head.data < ans)
                ans = this.head.data
            this.head = this.head.next
            i+=1
        }
        // Check whether Linked list have (K+1)th
        // Node or not
        if(this.head != null && this.head.next != null)
 
            // Update ans with minimum of 1st K-1
            // nodes and the (K+1)th Node.
            ans = Math.min(ans, this.head.next.data)
         
        return ans
    }
}
 
 
// Driver Code
 
let K = 4
 
// Create an empty singly linked list
let llist = new LinkedList()
 
llist.push(3)
llist.push(5)
llist.push(2)
llist.push(4)
llist.push(1)
 
// Call FirstNode function
document.write(llist.FirstNode(K),"</br>")
 
// This code is contributed by shinjanpatra
 
</script>

1

Complejidad temporal: O(K)
Espacio auxiliar: O(1)