Dada una lista enlazada XOR , la tarea es eliminar el Node al final de la lista enlazada XOR .
Ejemplos:
Entrada: 4<–>7<–>9<–>7
Salida: 4<–>7<–>9
Explicación: Eliminar un Node desde el final modifica la lista enlazada XOR dada a 4<–>7<–>9Entrada: 10
Salida: La lista está vacía
Explicación: Después de eliminar el único Node presente en la Lista enlazada XOR, la lista queda vacía.
Enfoque: La idea para resolver este problema es recorrer la lista enlazada XOR hasta llegar al último Node y actualizar la dirección de su Node anterior. Siga los pasos a continuación para resolver el problema:
- Si la lista enlazada XOR está vacía, imprima «La lista está vacía «.
- Atraviese la lista enlazada XOR hasta llegar al último Node de la lista enlazada.
- Actualiza la dirección de su Node anterior .
- Borra el último Node de la memoria .
- Si la lista queda vacía después de eliminar el último Node, imprima «La lista está vacía» . De lo contrario, imprima los Nodes restantes de la lista enlazada.
A continuación se muestra la implementación del enfoque anterior:
C
// C program for 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 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)
{
// 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 delete the last node
// present in the XOR Linked List
struct Node* delEnd(struct Node** head)
{
// Base condition
if (*head == NULL)
printf("List is empty");
else {
// 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 (XOR(curr->nxp, prev) != NULL) {
// Forward traversal
next = XOR(prev, curr->nxp);
// Update prev
prev = curr;
// Update curr
curr = next;
}
// If the Linked List contains more than 1 node
if (prev != NULL)
prev->nxp = XOR(XOR(prev->nxp, curr), NULL);
// Otherwise
else
*head = NULL;
// Delete the last node from memory
free(curr);
}
// Returns head of new linked list
return *head;
}
// Driver Code
int main()
{
/* Create the XOR Linked List
head-->40<-->30<-->20<-->10 */
struct Node* head = NULL;
insert(&head, 10);
insert(&head, 20);
insert(&head, 30);
insert(&head, 40);
delEnd(&head);
// If the list had a single node
if (head == NULL)
printf("List is empty");
else
// Print the list after deletion
printList(&head);
return (0);
}
40 30 20
Complejidad temporal: O(N)
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