Dada una lista enlazada XOR , la tarea es intercambiar por pares los elementos de la lista enlazada XOR dada .
Ejemplos:
Entrada: 4 <-> 7 <-> 9 <-> 7
Salida: 7 <-> 4 <-> 7 <-> 9
Explicación:
el primer par de Nodes se intercambia para formar la secuencia {4, 7} y el segundo par de Nodes se intercambian para formar la secuencia {9, 7}.Entrada: 1 <-> 2 <-> 3
Salida: 2 <-> 1 <-> 3
Enfoque: el problema se puede resolver utilizando el concepto de elementos de intercambio por pares de una lista enlazada dada . La idea es atravesar la lista enlazada xor dada y seleccionar dos pares de Nodes adyacentes e intercambiarlos. Siga los pasos a continuación para resolver el problema:
- Atraviese la lista vinculada xor dada , mientras que el Node actual y el siguiente Node de la lista vinculada xor no son nulos
- En cada iteración, intercambie los datos del Node actual con el Node siguiente y actualice el puntero del Node siguiente y el Node actual.
- Finalmente, imprima la lista vinculada a xor
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;
};
void pairwiseswap(struct Node**);
void swap(int*, int*);
// 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 pairwise swap the nodes
// of the XOR-linked list
void pairwiseswap(struct Node** head)
{
// Stores pointer of current node
struct Node* curr = (*head);
// Stores pointer of previous node
struct Node* prev = NULL;
// Stores pointer of next node
struct Node* next = NULL;
// Traverse the XOR-linked list
while (curr != NULL
&& curr->nxp != XOR(prev, NULL)) {
next = XOR(prev, curr->nxp);
prev = curr;
curr = next;
// Swap the elements
swap(&prev->data, &curr->data);
// Update next
next = XOR(prev, curr->nxp);
// Update prev
prev = curr;
// Update curr
curr = next;
}
}
// Function to swap two numbers
void swap(int* a, int* b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// 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;
}
}
// Driver Code
int main()
{
/* Create following XOR Linked List
head -->7 –> 6 –>8 –> 11 –> 3 –> 1 –> 2 –> 0*/
struct Node* head = NULL;
insert(&head, 0);
insert(&head, 2);
insert(&head, 1);
insert(&head, 3);
insert(&head, 11);
insert(&head, 8);
insert(&head, 6);
insert(&head, 7);
// Swap the elements pairwise
pairwiseswap(&head);
// Print the new list
printList(&head);
return (0);
}
6 7 11 8 1 3 0 2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
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