Lista vinculada inversa dada en grupos de tamaños específicos dados

Posted on by Rudeus Greyrat

Dada la lista enlazada y una array arr[] de tamaño N , la tarea es invertir todos los arr[i] Nodes de la lista a la vez (0 ≤ i < N) .

Nota: si el número de Nodes en la lista es mayor que la suma de la array, los Nodes restantes permanecerán como están.

Ejemplos:

Entrada: cabeza = 1->2->3->4->5->6->7->8->9, arr[] = {2, 3, 3}
Salida: 2->1->5 ->4->3->8->7->6->9
Explicación: El primer grupo de tamaño 2 es 1->2. Al invertir se convierte en 2->1.
El siguiente grupo de tamaño 3 es 3->4->5 que al invertir se convierte en 5->4->3.
El último grupo de tamaño 3 es 6->7->8 que al invertir se convierte en 8->7->6.

Entrada: cabeza = 6->8->7, arr[] = {1, 2}
Salida: 6->7->8

 

Enfoque: La solución al problema se basa en la idea de seleccionar grupos de Nodes de tamaño arr[i] y considerar cada sublista como una lista enlazada individual y utilizar el concepto de lista enlazada inversa .

Siga la ilustración a continuación para una mejor comprensión:

Ilustración:

reverso(cabeza, arr, n, índice)

Siga los pasos mencionados a continuación para implementar la idea:

  • Atraviesa la array desde i = 0 hasta N :
    • Invierta la sublista de tamaño arr[i] .
      • Mientras invierte la sublista, para cada Node, intercambie los punteros que apuntan al siguiente Node y al Node anterior.
  • Si se llega al final de la array, detenga la iteración y devuelva el puntero principal de la lista final.

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

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a Binary Tree Node
struct Node {
    int data;
        Node* next;
        Node(int d)
        {
            data = d;
            next = NULL;
        }
};
 
struct LinkedList {
    Node* head;
    LinkedList() { head = NULL; }
     
 // Function to reverse a node
    Node* reverse(Node* head, int arr[], int size, int index)
    {
        if (head == NULL)
            return NULL;
 
        Node* current = head;
        Node* next = NULL;
        Node* prev = NULL;
 
        int count = 0;
        while (current != NULL && index < size
               && count < arr[index]) {
            next = current->next;
            current->next = prev;
            prev = current;
            current = next;
            count++;
        }
 
        if (index >= size) {
            while (current != NULL) {
                next = current->next;
                current->next = prev;
                prev = current;
                current = next;
                count++;
            }
        }
 
        if (next != NULL) {
            head->next = reverse(next, arr, size, index + 1);
        }
 
        return prev;
    }
 
    // Function to push a node
     void push(int new_data)
    {
        Node* new_node = new Node(new_data);
        new_node->next = head;
        head = new_node;
    }
 
    // Function to print list
    void printList()
    {
        Node* temp = head;
        while (temp != NULL) {
            cout << temp->data << "->";
            temp = temp->next;
        }
        cout << endl;
    }
};
 
    // Driver program
    int main()
    {
        LinkedList llist;
        int arr[] = { 2, 3, 3 };
        int size = sizeof(arr)/sizeof(arr[0]);
     
        llist.push(9);
        llist.push(8);
        llist.push(7);
        llist.push(6);
        llist.push(5);
        llist.push(4);
        llist.push(3);
        llist.push(2);
        llist.push(1);
 
        llist.head
            = llist.reverse(llist.head, arr, size, 0);
 
        llist.printList();
         
        return 0;
         
}
 
// This code is contributed by jana_sayantan.

Java

// Java code to implement the approach
import java.io.*;
 
public class LinkedList {
    Node head;
 
    // Node Class
    static class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
 
    // Function to reverse a node
    Node reverse(Node head, int[] arr, int size, int index)
    {
        if (head == null)
            return null;
 
        Node current = head;
        Node next = null;
        Node prev = null;
 
        int count = 0;
        while (current != null && index < size
               && count < arr[index]) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
            count++;
        }
 
        if (index >= size) {
            while (current != null) {
                next = current.next;
                current.next = prev;
                prev = current;
                current = next;
                count++;
            }
        }
 
        if (next != null) {
            head.next = reverse(next, arr, size, index + 1);
        }
 
        return prev;
    }
 
    // Function to push a node
    public void push(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
 
    // Function to print list
    void printList()
    {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + "->");
            temp = temp.next;
        }
        System.out.println();
    }
 
    // Driver code
    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();
        int[] arr = { 2, 3, 3 };
        int size = arr.length;
 
        llist.push(9);
        llist.push(8);
        llist.push(7);
        llist.push(6);
        llist.push(5);
        llist.push(4);
        llist.push(3);
        llist.push(2);
        llist.push(1);
 
        llist.head
            = llist.reverse(llist.head, arr, size, 0);
 
        llist.printList();
    }
}
 
// This code is contributed by karandeep123.

Python3

# 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
     
 
    ## Function to push a node
    def push(self, new_data):
        new_node = Node(new_data);
        new_node.next = self.head;
        self.head = new_node;
 
    ## Function to print list
    def printList(self):
        temp = self.head
        while temp != None:
            print(temp.data, end='')
            if temp.next != None:
                print("->", end='')
            temp = temp.next
        print("\n")
 
    ## Function to reverse a node
    def reverse(self, head, arr, size, index):
        if (head == None):
            return None
 
        current = head
        next = None
        prev = None
 
        count = 0
        while current != None and index < size and count < arr[index]:
            next = current.next
            current.next = prev
            prev = current
            current = next
            count+=1
 
        if (index >= size):
            while current != None:
                next = current.next
                current.next = prev
                prev = current
                current = next
                count+=1
 
        if next != None:
            head.next = self.reverse(next, arr, size, index + 1);
 
        return prev;
 
# Driver Code
if __name__=='__main__':
 
    llist = LinkedList()
    arr = [2, 3, 3]
    size = len(arr)
 
    llist.push(9)
    llist.push(8)
    llist.push(7)
    llist.push(6)
    llist.push(5)
    llist.push(4)
    llist.push(3)
    llist.push(2)
    llist.push(1)
 
    llist.head = llist.reverse(llist.head, arr, size, 0)
 
    llist.printList()
 
 # This code is contributed by subhamgoyal2014.

C#

// C# code to implement the approach
 
using System;
using System.Linq;
public class LinkedList {
    Node head;
 
    // Node Class
    class Node {
        public int data;
        public Node next;
        public Node(int d)
        {
            data = d;
            next = null;
        }
    }
 
    // Function to reverse a node
    Node reverse(Node head, int[] arr,
                 int size, int index)
    {
        if (head == null)
            return null;
 
        Node current = head;
        Node next = null;
        Node prev = null;
 
        int count = 0;
        while (current != null
               && index < size
               && count < arr[index]) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
            count++;
        }
 
        if (index >= size) {
            while (current != null) {
                next = current.next;
                current.next = prev;
                prev = current;
                current = next;
                count++;
            }
        }
 
        if (next != null) {
            head.next
                = reverse(next, arr,
                          size, index + 1);
        }
 
        return prev;
    }
 
    // Function to push a node
    public void push(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
 
    // Function to print list
    void printList()
    {
        Node temp = head;
        while (temp != null) {
            Console.Write(temp.data + "->");
            temp = temp.next;
        }
        Console.WriteLine();
    }
 
    // Driver code
    static void Main()
    {
        LinkedList llist = new LinkedList();
        int[] arr = { 2, 3, 3 };
        int size = arr.Count();
 
        llist.push(9);
        llist.push(8);
        llist.push(7);
        llist.push(6);
        llist.push(5);
        llist.push(4);
        llist.push(3);
        llist.push(2);
        llist.push(1);
 
        llist.head
            = llist.reverse(llist.head,
                            arr, size, 0);
 
        llist.printList();
    }
}
// This code is contributed by Karandeep1234

Javascript

// Javascript code to implement the approach
 
// Structure of a Binary Tree Node
class Node {
        constructor(d)
        {
            this.data = d;
            this.next = null;
        }
};
 
// Function to reverse a node
function reverse(head,arr,size,index)
{
    if (head == null)
        return null;
 
    let current = head;
    let next = null;
    let prev = null;
 
    let count = 0;
    while (current != null && index < size
           && count < arr[index]) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
        count++;
    }
 
    if (index >= size) {
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
            count++;
        }
    }
 
    if (next != null) {
        head.next = reverse(next, arr, size, index + 1);
    }
 
    return prev;
}
class LinkedList {
    constructor() { this.head = null; }
     
     // Function to push a node
     push(new_data)
    {
        let new_node = new Node(new_data);
        new_node.next = this.head;
        this.head = new_node;
    }
 
    // Function to print list
    printList() {
        var curr = this.head;
        var str = "";
        while (curr) {
            str += curr.data + "->";
            curr = curr.next;
        }
        console.log(str);
    }
}
 
    // Driver program
        let llist= new LinkedList();
        let arr = [ 2, 3, 3 ];
        let size = 3;
     
        llist.push(9);
        llist.push(8);
        llist.push(7);
        llist.push(6);
        llist.push(5);
        llist.push(4);
        llist.push(3);
        llist.push(2);
        llist.push(1);
 
        llist.head
            = reverse(llist.head, arr, size, 0);
 
        llist.printList(); 
 
// This code is contributed by Ishan Khandelwal.
Producción

2->1->5->4->3->8->7->6->9->

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

Publicación traducida automáticamente

Artículo escrito por crypticj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *