Dada una lista doblemente enlazada y una lista circular sencillamente enlazada que contiene N Nodes, la tarea es eliminar todos los Nodes de cada lista que contiene elementos cuya paridad es par.
Ejemplo:
Entrada: CLL = 9 -> 11 -> 34 -> 6 -> 13 -> 21
Salida: 11 -> 13 -> 21
Explicación:
La lista circular enlazada individualmente contiene:
11 -> 1011, paridad = 3
9 -> 1001 , paridad = 2
34 -> 100010, paridad = 2
6 -> 110, paridad = 2
13 -> 1101, paridad = 3
21 -> 10101, paridad = 3
Aquí, la paridad para los Nodes que contienen 9, 34 y 6 son pares .
Por lo tanto, estos Nodes se han eliminado.Entrada: DLL = 18 <=> 15 <=> 8 <=> 9 <=> 14
Salida: 8 <=> 14
Explicación:
La lista enlazada contiene:
18 -> 10010, paridad = 2
15 -> 1111, paridad = 4
8 -> 1000, paridad = 1
9 -> 1001, paridad = 2
14 -> 1110, paridad = 3
Aquí, la paridad de los Nodes que contienen 18, 15 y 9 son pares.
Por lo tanto, estos Nodes se han eliminado.
Enfoque:
un enfoque simple es atravesar los Nodes de la lista uno por uno y para cada Node primero, encontrar la paridad para el valor presente en el Node iterando a través de cada bit y luego finalmente eliminar los Nodes cuya paridad es par.
Lista doblemente enlazada
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to remove all
// the Even Parity Nodes from a
// doubly linked list
#include <bits/stdc++.h>
using namespace std;
// Node of the doubly linked list
struct Node {
int data;
Node *prev, *next;
};
// Function to insert a node at the beginning
// of the Doubly Linked List
void push(Node** head_ref, int new_data)
{
// Allocate the node
Node* new_node
= (Node*)malloc(sizeof(struct Node));
// Insert the data
new_node->data = new_data;
// Since we are adding at the beginning,
// prev is always NULL
new_node->prev = NULL;
// Link the old list off the new node
new_node->next = (*head_ref);
// Change the prev of
// head node to new node
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
// Move the head to point
// to the new node
(*head_ref) = new_node;
}
// Function that returns true if count
// of set bits in x is even
bool isEvenParity(int x)
{
// parity will store the
// count of set bits
int parity = 0;
while (x != 0) {
if (x & 1)
parity++;
x = x >> 1;
}
if (parity % 2 == 0)
return true;
else
return false;
}
// Function to delete a node
// in a Doubly Linked List.
// head_ref --> pointer to head node pointer.
// del --> pointer to node to be deleted
void deleteNode(Node** head_ref, Node* del)
{
// Base case
if (*head_ref == NULL || del == NULL)
return;
// If the node to be
// deleted is head node
if (*head_ref == del)
*head_ref = del->next;
// Change next only if node to be
// deleted is not the last node
if (del->next != NULL)
del->next->prev = del->prev;
// Change prev only if node to be
// deleted is not the first node
if (del->prev != NULL)
del->prev->next = del->next;
// Finally, free the memory
// occupied by del
free(del);
return;
}
// Function to to remove all
// the Even Parity Nodes from a
// doubly linked list
void deleteEvenParityNodes(
Node** head_ref)
{
Node* ptr = *head_ref;
Node* next;
// Iterating through
// the linked list
while (ptr != NULL) {
next = ptr->next;
// If node's data's parity
// is even
if (isEvenParity(ptr->data))
deleteNode(head_ref, ptr);
ptr = next;
}
}
// Function to print nodes in a
// given doubly linked list
void printList(Node* head)
{
if (head == NULL) {
cout << "Empty list\n";
return;
}
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Driver Code
int main()
{
Node* head = NULL;
// Create the doubly linked list
// 18 <-> 15 <-> 8 <-> 9 <-> 14
push(&head, 14);
push(&head, 9);
push(&head, 8);
push(&head, 15);
push(&head, 18);
// Uncomment to view the list
// cout << "Original List: ";
// printList(head);
deleteEvenParityNodes(&head);
// Modified List
printList(head);
}
Java
/*package whatever //do not write package name here */
import java.io.*;
public class GFG {
static Node head; // head of linked list
// Node of the doubly linked list
class Node {
int data;
Node prev;
Node next;
// Constructor to create a new node
// next and prev is by default initialized as null
Node(int d) { data = d; }
}
// Add a node at the end of the list
public void append(int new_data)
{
/* 1. allocate node
* 2. put in the data */
Node new_node = new Node(new_data);
Node last = head; /* used in step 5*/
/* 3. This new node is going to be the last node, so
* make next of it as NULL*/
new_node.next = null;
/* 4. If the Linked List is empty, then make the new
* node as head */
if (head == null) {
new_node.prev = null;
head = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last.next != null)
last = last.next;
/* 6. Change the next of last node */
last.next = new_node;
/* 7. Make last node as previous of new node */
new_node.prev = last;
}
// Function to delete a node in a Doubly Linked List.
// head_ref --> pointer to head node pointer.
// del --> data of node to be deleted.
public static void deleteNode(Node del)
{
// Base case
if (head == null || del == null) {
return;
}
// If node to be deleted is head node
if (head == del) {
head = del.next;
}
// Change next only if node to be deleted
// is NOT the last node
if (del.next != null) {
del.next.prev = del.prev;
}
// Change prev only if node to be deleted
// is NOT the first node
if (del.prev != null) {
del.prev.next = del.next;
}
// Finally, free the memory occupied by del
return;
}
// Function that returns true if count
// of set bits in x is even
public static boolean isEvenParity(int x)
{
// parity will store the
// count of set bits
int parity = 0;
while (x != 0) {
if (x % 2 == 1)
parity++;
x = x >> 1;
}
if (parity % 2 == 0)
return true;
else
return false;
}
// Function to to remove all
// the Even Parity Nodes from a
// doubly linked list
public static void deleteEvenParityNodes()
{
Node ptr = head;
Node next;
// Iterating through
// the linked list
while (ptr != null) {
next = ptr.next;
// If node's data's parity
// is even
if (isEvenParity(ptr.data)) {
deleteNode(ptr);
}
ptr = next;
}
}
// This function prints contents of
// linked list starting from the given node
public static void printlist()
{
Node node = head;
System.out.println(
"Traversal in forward Direction");
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
/* Driver program to test above functions*/
public static void main(String[] args)
{
/* Start with the empty list */
GFG dll = new GFG();
// Create the doubly linked list
// 14 <-> 9 <-> 8 <-> 15 <-> 18
dll.append(18);
dll.append(15);
dll.append(8);
dll.append(9);
dll.append(14);
// Uncomment to view the list
// cout << "Original List: ";
// printList();
deleteEvenParityNodes();
// Modified List
printlist();
}
}
// This code is contributed by rj13to.
Python3
# Python3 implementation to remove all
# the Even Parity Nodes from a
# doubly linked list
# Node of the doubly linked list
class Node:
def __init__(self):
self.data = 0
self.prev = None
self.next = None
# Function to insert a node at the
# beginning of the Doubly Linked List
def push(head_ref, new_data):
# Allocate the node
new_node = Node()
# Insert the data
new_node.data = new_data
# Since we are adding at the
# beginning, prev is always None
new_node.prev = None
# Link the old list off the new node
new_node.next = (head_ref)
# Change the prev of
# head node to new node
if ((head_ref) != None):
(head_ref).prev = new_node
# Move the head to point
# to the new node
(head_ref) = new_node
return head_ref
# Function that returns true if count
# of set bits in x is even
def isEvenParity(x):
# parity will store the
# count of set bits
parity = 0
while (x != 0):
if (x & 1):
parity += 1
x = x >> 1
if (parity % 2 == 0):
return True
else:
return False
# Function to delete a node
# in a Doubly Linked List.
# head_ref -. pointer to head node pointer.
# delt -. pointer to node to be deleted
def deleteNode(head_ref, delt):
# Base case
if (head_ref == None or delt == None):
return
# If the node to be
# deleted is head node
if (head_ref == delt):
head_ref = delt.next
# Change next only if node to be
# deleted is not the last node
if (delt.next != None):
delt.next.prev = delt.prev
# Change prev only if node to be
# deleted is not the first node
if (delt.prev != None):
delt.prev.next = delt.next
# Finally, free the memory
# occupied by delt
del(delt)
return head_ref
# Function to to remove all
# the Even Parity Nodes from a
# doubly linked list
def deleteEvenParityNodes(head_ref):
ptr = head_ref
next = None
# Iterating through
# the linked list
while (ptr != None):
next = ptr.next
# If node's data's parity
# is even
if (isEvenParity(ptr.data)):
head_ref = deleteNode(head_ref, ptr)
ptr = next
return head_ref
# Function to print nodes in a
# given doubly linked list
def printList(head):
if (head == None):
print("Empty list\n")
return
while (head != None):
print(head.data, end = ' ')
head = head.next
# Driver Code
if __name__=='__main__':
head = None
# Create the doubly linked list
# 18 <. 15 <. 8 <. 9 <. 14
head = push(head, 14)
head = push(head, 9)
head = push(head, 8)
head = push(head, 15)
head = push(head, 18)
# Uncomment to view the list
# cout << "Original List: ";
# printList(head);
head = deleteEvenParityNodes(head)
# Modified List
printList(head)
# This code is contributed by rutvik_56
C#
/*package whatever //do not write package name here */
using System;
using System.Collections.Generic;
public class GFG {
static Node head; // head of linked list
// Node of the doubly linked list
class Node {
public int data;
public Node prev;
public Node next;
// Constructor to create a new node
// next and prev is by default initialized as null
public Node(int d) { data = d; }
}
// Add a node at the end of the list
public void append(int new_data)
{
/* 1. allocate node
* 2. put in the data */
Node new_node = new Node(new_data);
Node last = head; /* used in step 5*/
/* 3. This new node is going to be the last node, so
* make next of it as NULL*/
new_node.next = null;
/* 4. If the Linked List is empty, then make the new
* node as head */
if (head == null) {
new_node.prev = null;
head = new_node;
return;
}
/* 5. Else traverse till the last node */
while (last.next != null)
last = last.next;
/* 6. Change the next of last node */
last.next = new_node;
/* 7. Make last node as previous of new node */
new_node.prev = last;
}
// Function to delete a node in a Doubly Linked List.
// head_ref --> pointer to head node pointer.
// del --> data of node to be deleted.
static void deleteNode(Node del)
{
// Base case
if (head == null || del == null) {
return;
}
// If node to be deleted is head node
if (head == del) {
head = del.next;
}
// Change next only if node to be deleted
// is NOT the last node
if (del.next != null) {
del.next.prev = del.prev;
}
// Change prev only if node to be deleted
// is NOT the first node
if (del.prev != null) {
del.prev.next = del.next;
}
// Finally, free the memory occupied by del
return;
}
// Function that returns true if count
// of set bits in x is even
public static bool isEvenParity(int x)
{
// parity will store the
// count of set bits
int parity = 0;
while (x != 0) {
if (x % 2 == 1)
parity++;
x = x >> 1;
}
if (parity % 2 == 0)
return true;
else
return false;
}
// Function to to remove all
// the Even Parity Nodes from a
// doubly linked list
public static void deleteEvenParityNodes()
{
Node ptr = head;
Node next;
// Iterating through
// the linked list
while (ptr != null) {
next = ptr.next;
// If node's data's parity
// is even
if (isEvenParity(ptr.data)) {
deleteNode(ptr);
}
ptr = next;
}
}
// This function prints contents of
// linked list starting from the given node
public static void printlist()
{
Node node = head;
Console.WriteLine(
"Traversal in forward Direction");
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
/* Driver program to test above functions*/
public static void Main(String[] args)
{
/* Start with the empty list */
GFG dll = new GFG();
// Create the doubly linked list
// 14 <-> 9 <-> 8 <-> 15 <-> 18
dll.append(18);
dll.append(15);
dll.append(8);
dll.append(9);
dll.append(14);
// Uncomment to view the list
// cout << "Original List: ";
// printList();
deleteEvenParityNodes();
// Modified List
printlist();
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript implementation to remove all
// the Even Parity Nodes from a
// doubly linked list
// Node of the doubly linked list
class Node{
constructor(){
this.data = 0
this.prev = null
this.next = null
}
}
// Function to insert a node at the
// beginning of the Doubly Linked List
function push(head_ref, new_data){
// Allocate the node
let new_node = new Node()
// Insert the data
new_node.data = new_data
// Since we are adding at the
// beginning, prev is always null
new_node.prev = null
// Link the old list off the new node
new_node.next = head_ref
// Change the prev of
// head node to new node
if (head_ref != null)
head_ref.prev = new_node
// Move the head to point
// to the new node
head_ref = new_node
return head_ref
}
// Function that returns true if count
// of set bits in x is even
function isEvenParity(x){
// parity will store the
// count of set bits
let parity = 0
while (x != 0){
if (x & 1)
parity += 1
x = x >> 1
}
if (parity % 2 == 0)
return true
else
return false
}
// Function to delete a node
// in a Doubly Linked List.
// head_ref -. pointer to head node pointer.
// delt -. pointer to node to be deleted
function deleteNode(head_ref, delt){
// Base case
if (head_ref == null || delt == null)
return
// If the node to be
// deleted is head node
if (head_ref == delt)
head_ref = delt.next
// Change next only if node to be
// deleted is not the last node
if (delt.next != null)
delt.next.prev = delt.prev
// Change prev only if node to be
// deleted is not the first node
if (delt.prev != null)
delt.prev.next = delt.next
// Finally, free the memory
// occupied by delt
delt = null
return head_ref
}
// Function to to remove all
// the Even Parity Nodes from a
// doubly linked list
function deleteEvenParityNodes(head_ref){
let ptr = head_ref
let next = null
// Iterating through
// the linked list
while (ptr != null){
next = ptr.next
// If node's data's parity
// is even
if (isEvenParity(ptr.data))
head_ref = deleteNode(head_ref, ptr)
ptr = next
}
return head_ref
}
// Function to print nodes in a
// given doubly linked list
function printList(head){
if (head == null){
document.write("Empty list","</br>")
return
}
while (head != null){
document.write(head.data,' ')
head = head.next
}
}
// Driver Code
let head = new Node()
// Create the doubly linked list
// 18 <. 15 <. 8 <. 9 <. 14
head = push(head, 14)
head = push(head, 9)
head = push(head, 8)
head = push(head, 15)
head = push(head, 18)
// Uncomment to view the list
// cout << "Original List: ";
// printList(head);
head = deleteEvenParityNodes(head)
// Modified List
printList(head)
// This code is contributed by shinjanpatra
</script>
Producción:
8 14
Lista circular enlazada individualmente
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to remove all
// the Even Parity Nodes from a
// circular singly linked list
#include <bits/stdc++.h>
using namespace std;
// Structure for a node
struct Node {
int data;
struct Node* next;
};
// Function to insert a node at the beginning
// of a Circular linked list
void push(struct Node** head_ref, int data)
{
// Create a new node
// and make head as next
// of it.
struct Node* ptr1
= (struct Node*)malloc(
sizeof(struct Node));
struct Node* temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;
// If linked list is not NULL then
// set the next of last node
if (*head_ref != NULL) {
// Find the node before head
// and update next of it.
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
// Point for the first node
ptr1->next = ptr1;
*head_ref = ptr1;
}
// Function to delete the node from a
// Circular Linked list
void deleteNode(
Node*& head_ref, Node* del)
{
// If node to be deleted is head node
if (head_ref == del)
head_ref = del->next;
struct Node* temp = head_ref;
// Traverse list till not found
// delete node
while (temp->next != del) {
temp = temp->next;
}
// Copy the address of the node
temp->next = del->next;
// Finally, free the memory
// occupied by del
free(del);
return;
}
// Function that returns true if count
// of set bits in x is even
bool isEvenParity(int x)
{
// parity will store the
// count of set bits
int parity = 0;
while (x != 0) {
if (x & 1)
parity++;
x = x >> 1;
}
if (parity % 2 == 0)
return true;
else
return false;
}
// Function to delete all
// the Even Parity Nodes
// from the singly circular linked list
void deleteEvenParityNodes(Node*& head)
{
if (head == NULL)
return;
if (head == head->next) {
if (isEvenParity(head->data))
head = NULL;
return;
}
struct Node* ptr = head;
struct Node* next;
// Traverse the list till the end
do {
next = ptr->next;
// If the node's data has even parity,
// delete node 'ptr'
if (isEvenParity(ptr->data))
deleteNode(head, ptr);
// Point to the next node
ptr = next;
} while (ptr != head);
if (head == head->next) {
if (isEvenParity(head->data))
head = NULL;
return;
}
}
// Function to print nodes in a
// given Circular linked list
void printList(struct Node* head)
{
if (head == NULL) {
cout << "Empty List\n";
return;
}
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
}
// Driver code
int main()
{
// Initialize lists as empty
struct Node* head = NULL;
// Created linked list will be
// 11->9->34->6->13->21
push(&head, 21);
push(&head, 13);
push(&head, 6);
push(&head, 34);
push(&head, 9);
push(&head, 11);
deleteEvenParityNodes(head);
printList(head);
return 0;
}
Java
// Java program to remove all
// the Even Parity Nodes from a
// circular singly linked list
class GFG{
// Structure for a node
static class Node
{
int data;
Node next;
};
// Function to insert a node at
// the beginning of a Circular
// linked list
static Node push(Node head_ref, int data)
{
// Create a new node
// and make head as next
// of it.
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
// If linked list is not null then
// set the next of last node
if (head_ref != null)
{
// Find the node before head
// and update next of it.
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
// Point for the first node
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
// Function to delete the node
// from a Circular Linked list
static void deleteNode(Node head_ref,
Node del)
{
// If node to be deleted is
// head node
if (head_ref == del)
head_ref = del.next;
Node temp = head_ref;
// Traverse list till not found
// delete node
while (temp.next != del)
{
temp = temp.next;
}
// Copy the address of the node
temp.next = del.next;
// Finally, free the memory
// occupied by del
System.gc();
return;
}
// Function that returns true if count
// of set bits in x is even
static boolean isEvenParity(int x)
{
// Parity will store the
// count of set bits
int parity = 0;
while (x != 0)
{
if ((x & 1) != 0)
parity++;
x = x >> 1;
}
if (parity % 2 == 0)
return true;
else
return false;
}
// Function to delete all the
// Even Parity Nodes from the
// singly circular linked list
static void deleteEvenParityNodes(Node head)
{
if (head == null)
return;
if (head == head.next)
{
if (isEvenParity(head.data))
head = null;
return;
}
Node ptr = head;
Node next;
// Traverse the list till the end
do
{
next = ptr.next;
// If the node's data has
// even parity, delete node 'ptr'
if (isEvenParity(ptr.data))
deleteNode(head, ptr);
// Point to the next node
ptr = next;
} while (ptr != head);
if (head == head.next)
{
if (isEvenParity(head.data))
head = null;
return;
}
}
// Function to print nodes in a
// given Circular linked list
static void printList(Node head)
{
if (head == null)
{
System.out.print("Empty List\n");
return;
}
Node temp = head;
if (head != null)
{
do
{
System.out.printf("%d ", temp.data);
temp = temp.next;
} while (temp != head);
}
}
// Driver code
public static void main(String[] args)
{
// Initialize lists as empty
Node head = null;
// Created linked list will be
// 11.9.34.6.13.21
head = push(head, 21);
head = push(head, 13);
head = push(head, 6);
head = push(head, 34);
head = push(head, 9);
head = push(head, 11);
deleteEvenParityNodes(head);
printList(head);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to remove all
# the Even Parity Nodes from a
# circular singly linked list
# Structure for a node
class Node:
def __init__(self):
self.data = 0
self.next = None
# Function to insert a node at the beginning
# of a Circular linked list
def push(head_ref, data):
# Create a new node
# and make head as next
# of it.
ptr1 = Node()
temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
# If linked list is not None then
# set the next of last node
if (head_ref != None):
# Find the node before head
# and update next of it.
while (temp.next != head_ref):
temp = temp.next;
temp.next = ptr1;
else:
# Point for the first node
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref
# Function to delete the node from a
# Circular Linked list
def deleteNode( head_ref, delt):
# If node to be deleted is head node
if (head_ref == delt):
head_ref = delt.next;
temp = head_ref;
# Traverse list till not found
# delete node
while (temp.next != delt):
temp = temp.next;
# Copy the address of the node
temp.next = delt.next;
# Finally, free the memory
# occupied by delt
del(delt);
return head_ref;
# Function that returns true if count
# of set bits in x is even
def isEvenParity(x):
# parity will store the
# count of set bits
parity = 0;
while (x != 0):
if (x & 1) != 0:
parity += 1
x = x >> 1;
if (parity % 2 == 0):
return True;
else:
return False;
# Function to delete all
# the Even Parity Nodes
# from the singly circular linked list
def deleteEvenParityNodes(head):
if (head == None):
return head;
if (head == head.next):
if (isEvenParity(head.data)):
head = None;
return head;
ptr = head;
next = None
# Traverse the list till the end
while True:
next = ptr.next;
# If the node's data has even parity,
# delete node 'ptr'
if (isEvenParity(ptr.data)):
head=deleteNode(head, ptr);
# Point to the next node
ptr = next;
if(ptr == head):
break
if (head == head.next):
if (isEvenParity(head.data)):
head = None;
return head;
return head;
# Function to print nodes in a
# given Circular linked list
def printList(head):
if (head == None):
print("Empty List")
return;
temp = head;
if (head != None):
while True:
print(temp.data, end=' ')
temp = temp.next
if temp == head:
break
# Driver code
if __name__=='__main__':
# Initialize lists as empty
head = None;
# Created linked list will be
# 11.9.34.6.13.21
head=push(head, 21);
head=push(head, 13);
head=push(head, 6);
head=push(head, 34);
head=push(head, 9);
head=push(head, 11);
head=deleteEvenParityNodes(head);
printList(head);
# This code is contributed by pratham_76
C#
// C# program to remove all
// the Even Parity Nodes from a
// circular singly linked list
using System;
class GFG{
// Structure for a node
public class Node
{
public int data;
public Node next;
};
// Function to insert a node at
// the beginning of a Circular
// linked list
static Node push(Node head_ref,
int data)
{
// Create a new node
// and make head as next
// of it.
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
// If linked list is not
// null then set the next
// of last node
if (head_ref != null)
{
// Find the node before head
// and update next of it.
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
// Point for the first node
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
// Function to delete the node
// from a Circular Linked list
static void deleteNode(Node head_ref,
Node del)
{
// If node to be deleted is
// head node
if (head_ref == del)
head_ref = del.next;
Node temp = head_ref;
// Traverse list till not
// found delete node
while (temp.next != del)
{
temp = temp.next;
}
// Copy the address of
// the node
temp.next = del.next;
return;
}
// Function that returns true
// if count of set bits in x
// is even
static bool isEvenParity(int x)
{
// Parity will store the
// count of set bits
int parity = 0;
while (x != 0)
{
if ((x & 1) != 0)
parity++;
x = x >> 1;
}
if (parity % 2 == 0)
return true;
else
return false;
}
// Function to delete all the
// Even Parity Nodes from the
// singly circular linked list
static void deleteEvenParityNodes(Node head)
{
if (head == null)
return;
if (head == head.next)
{
if (isEvenParity(head.data))
head = null;
return;
}
Node ptr = head;
Node next;
// Traverse the list
// till the end
do
{
next = ptr.next;
// If the node's data has
// even parity, delete node 'ptr'
if (isEvenParity(ptr.data))
deleteNode(head, ptr);
// Point to the next node
ptr = next;
} while (ptr != head);
if (head == head.next)
{
if (isEvenParity(head.data))
head = null;
return;
}
}
// Function to print nodes in a
// given Circular linked list
static void printList(Node head)
{
if (head == null)
{
Console.Write("Empty List\n");
return;
}
Node temp = head;
if (head != null)
{
do
{
Console.Write(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
// Driver code
public static void Main(String[] args)
{
// Initialize lists as empty
Node head = null;
// Created linked list will be
// 11.9.34.6.13.21
head = push(head, 21);
head = push(head, 13);
head = push(head, 6);
head = push(head, 34);
head = push(head, 9);
head = push(head, 11);
deleteEvenParityNodes(head);
printList(head);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to remove all
// the Even Parity Nodes from a
// circular singly linked list
// Structure for a node
class Node
{
constructor(val)
{
this.data = val;
this.next = null;
}
}
// Function to insert a node at
// the beginning of a Circular
// linked list
function push(head_ref, data)
{
// Create a new node
// and make head as next
// of it.
var ptr1 = new Node();
var temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
// If linked list is not null then
// set the next of last node
if (head_ref != null)
{
// Find the node before head
// and update next of it.
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
// Point for the first node
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
// Function to delete the node
// from a Circular Linked list
function deleteNode(head_ref, del)
{
// If node to be deleted is
// head node
if (head_ref == del)
head_ref = del.next;
var temp = head_ref;
// Traverse list till not found
// delete node
while (temp.next != del)
{
temp = temp.next;
}
// Copy the address of the node
temp.next = del.next;
// Finally, free the memory
// occupied by del
return;
}
// Function that returns true if count
// of set bits in x is even
function isEvenParity(x)
{
// Parity will store the
// count of set bits
var parity = 0;
while (x != 0)
{
if ((x & 1) != 0)
parity++;
x = x >> 1;
}
if (parity % 2 == 0)
return true;
else
return false;
}
// Function to delete all the
// Even Parity Nodes from the
// singly circular linked list
function deleteEvenParityNodes(head)
{
if (head == null)
return;
if (head == head.next)
{
if (isEvenParity(head.data))
head = null;
return;
}
var ptr = head;
var next;
// Traverse the list till the end
do
{
next = ptr.next;
// If the node's data has
// even parity, delete node 'ptr'
if (isEvenParity(ptr.data))
deleteNode(head, ptr);
// Point to the next node
ptr = next;
} while (ptr != head);
if (head == head.next)
{
if (isEvenParity(head.data))
head = null;
return;
}
}
// Function to print nodes in a
// given Circular linked list
function printList(head)
{
if (head == null)
{
document.write("Empty List\n");
return;
}
var temp = head;
if (head != null)
{
do
{
document.write(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
// Driver code
// Initialize lists as empty
var head = null;
// Created linked list will be
// 11.9.34.6.13.21
head = push(head, 21);
head = push(head, 13);
head = push(head, 6);
head = push(head, 34);
head = push(head, 9);
head = push(head, 11);
deleteEvenParityNodes(head);
printList(head);
// This code is contributed by gauravrajput1
</script>
Producción:
11 13 21
Complejidad de tiempo: O(K*N) , donde N es el tamaño de la lista enlazada y K es el número de bits en el número máximo presente en la lista enlazada.
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA