Dada una lista enlazada XOR , la tarea es encontrar el Node medio de la lista enlazada XOR dada .
Ejemplos:
Entrada: 4 –> 7 –> 5
Salida: 7
Explicación:
El Node medio de la lista XOR dada es 7.Entrada: 4 –> 7 –> 5 –> 1
Salida: 7 5
Explicación:
Los dos Nodes medios de la lista enlazada XOR con un número par de Nodes son 7 y 5.
Enfoque: siga los pasos a continuación para resolver el problema:
- Recorrer a (Longitud / 2) Node de la Lista Vinculada.
- Si se encuentra que el número de Nodes es impar, imprima (Longitud + 1) / 2º Node como el único Node medio.
- Si se encuentra que el número de Nodes es par, imprima Longitud / 2º Node y (Longitud / 2) + 1º Node como los Nodes intermedios.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
#include <inttypes.h>
using namespace std;
// 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 = new 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
= new 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 the middle node
int printMiddle(struct Node** head, int len)
{
int count = 0;
// 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;
int middle = (int)len / 2;
// Traverse XOR linked list
while (count != middle) {
// Forward traversal
next = XOR(prev, curr->nxp);
// Update prev
prev = curr;
// Update curr
curr = next;
count++;
}
// If the length of the
// linked list is odd
if (len & 1) {
cout << curr->data << " ";
}
// If the length of the
// linked list is even
else {
cout << prev->data << " " << curr->data << " ";
}
}
// Driver Code
int main()
{
/* Create following XOR Linked List
head --> 4 –> 7 –> 5 */
struct Node* head = NULL;
insert(&head, 4);
insert(&head, 7);
insert(&head, 5);
printMiddle(&head, 3);
return (0);
}
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 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 the middle node
int printMiddle(struct Node** head, int len)
{
int count = 0;
// 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;
int middle = (int)len / 2;
// Traverse XOR linked list
while (count != middle) {
// Forward traversal
next = XOR(prev, curr->nxp);
// Update prev
prev = curr;
// Update curr
curr = next;
count++;
}
// If the length of the
// linked list is odd
if (len & 1) {
printf("%d", curr->data);
}
// If the length of the
// linked list is even
else {
printf("%d %d", prev->data,
curr->data);
}
}
// Driver Code
int main()
{
/* Create following XOR Linked List
head --> 4 –> 7 –> 5 */
struct Node* head = NULL;
insert(&head, 4);
insert(&head, 7);
insert(&head, 5);
printMiddle(&head, 3);
return (0);
}
Producción:
7
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