Dada una lista enlazada XOR , la tarea es eliminar el primer Node de la lista enlazada XOR.
Ejemplos:
Entrada: XLL = 4 < – > 7 < – > 9 < – > 7
Salida: 7 < – > 9 < – > 7
Explicación:
Eliminar el primer Node de la lista enlazada XOR modifica XLL a 7 < – > 9 < – > 7Entrada: XLL = NULL
Salida: La lista está vacía
Enfoque: la idea es actualizar el Node principal de la lista vinculada XOR al segundo Node de la lista vinculada XOR y eliminar la memoria asignada para el primer Node. Siga los pasos a continuación para resolver el problema:
- Compruebe si la lista enlazada XOR está vacía o no. Si se encuentra que es cierto, imprima «La lista está vacía» .
- De lo contrario, actualice el Node principal de la lista vinculada XOR al segundo Node de la lista vinculada.
- Elimine el primer Node de la memoria.
A continuación se muestra la implementación del enfoque anterior:
C
// C program to implement
// the above approach
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
// Structure of a node
// in XOR linked list
struct Node {
// Stores data value
// of a node
int data;
// Stores XOR of previous
// pointer and next pointer
struct Node* nxp;
};
// Function to find the XOR
// of address two nodes
struct Node* XOR(struct Node* a,
struct Node* b)
{
return (struct Node*)((uintptr_t)(a) ^ (uintptr_t)(b));
}
// Function to insert a node with
// given value at given position
struct Node* insert(struct Node** head,
int value)
{
// Check If XOR linked list
// is empty
if (*head == NULL) {
// Initialize a new Node
struct Node* node
= (struct Node*)malloc(sizeof(struct Node));
// Stores data value in
// the node
node->data = value;
// Stores XOR of previous
// and next pointer
node->nxp = XOR(NULL, NULL);
// Update pointer of head node
*head = node;
}
// If the XOR linked list
// is not empty
else {
// Stores the address
// of current node
struct Node* curr = *head;
// Stores the address
// of previous node
struct Node* prev = NULL;
// Initialize a new Node
struct Node* node
= (struct Node*)malloc(
sizeof(struct Node));
// Update curr node address
curr->nxp = XOR(node,
XOR(NULL, curr->nxp));
// Update new node address
node->nxp = XOR(NULL, curr);
// Update head
*head = node;
// Update data value of
// current node
node->data = value;
}
return *head;
}
// Function to print elements of
// the XOR Linked List
void printList(struct Node** head)
{
// Stores XOR pointer
// in current node
struct Node* curr = *head;
// Stores XOR pointer of
// in previous Node
struct Node* prev = NULL;
// Stores XOR pointer of
// in next node
struct Node* next;
// Traverse XOR linked list
while (curr != NULL) {
// Print current node
printf("%d ", curr->data);
// Forward traversal
next = XOR(prev, curr->nxp);
// Update prev
prev = curr;
// Update curr
curr = next;
}
}
// Function to remove the first node form
// the given linked list
struct Node* delBeginning(struct Node** head)
{
// If list is empty
if (*head == NULL)
printf("List Is Empty");
else {
// Store the node to be deleted
struct Node* temp = *head;
// Update the head pointer
*head = XOR(NULL, temp->nxp);
// When the linked list
// contains only one node
if (*head != NULL) {
// Update head node address
(*head)->nxp
= XOR(NULL, XOR(temp,
(*head)->nxp));
}
free(temp);
}
return *head;
}
// Driver Code
int main()
{
/* Create following XOR Linked List
head-->40<-->30<-->20<-->10 */
struct Node* head = NULL;
insert(&head, 10);
insert(&head, 20);
insert(&head, 30);
insert(&head, 40);
// Delete the first node
delBeginning(&head);
/* Print the following XOR Linked List
head-->30<-->20<-->10 */
printList(&head);
return (0);
}
30 20 10
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por debarpan_bose_chowdhury y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA