Remove all the Even digit sum nodes from a circular linked list
The problem involves removing nodes from a circular linked list based on whether the sum of the digits in their data is even. If the sum of digits is even, the node is removed from the list; otherwise, it is retained. This problem demonstrates how to manipulate circular linked lists and evaluate digit sums.
Problem Statement
Given a circular linked list, the problem is to remove all nodes from the list whose data has an even digit sum.
Example
Consider the circular linked list:
Linked List: 13 -> 12 -> 32 -> 1 -> 14 -> 91 -> 27 -> 124 -> 88
After removing nodes with even digit sum:
Result: 12 -> 32 -> 1 -> 14 -> 27 -> 124
Idea to Solve the Problem
To solve the problem of removing nodes with even digit sums from a circular linked list, follow these steps:
- Initialize pointers
temp
andauxiliary
to the head node of the circular linked list. - Traverse the circular linked list using the
temp
pointer. - For each node, compute the sum of its digits using the
digitSum
function. - If the sum is even, remove the current node using the following logic:
- Update the
auxiliary
pointer to point to the next node. - Update the next pointer of the previous node to skip the current node.
- If the current node is the head node, update the head pointer to the next node.
- If the current node is the tail node, update the tail pointer to the previous node.
- Free the memory allocated for the removed node.
- Update the
- If the sum is odd, move the
auxiliary
pointer to the current node and continue to the next node. - Continue this process until the traversal completes and the
temp
pointer points back to the head node.
Pseudocode
function removeEvenDigitSumNode():
if head is null:
return
temp = head
auxiliary = head
point = null
while temp is not null:
sum = digitSum(temp.data)
if (sum & 1) is equal to 0:
auxiliary = temp
temp = temp.next
if auxiliary is equal to head:
if auxiliary is equal to tail:
tail = null
head = null
temp = null
point = null
else:
head = temp
tail.next = temp
else if auxiliary is equal to tail:
if point is not null:
point.next = head
tail = point
else:
if point is not null:
point.next = temp
auxiliary = null
else:
point = temp
temp = temp.next
if temp is equal to head:
temp = null
Algorithm Explanation
- If the circular linked list is empty, return.
- Initialize pointers
temp
andauxiliary
to the head node of the circular linked list. Also, initializepoint
to null. - Traverse the circular linked list using the
temp
pointer. - For each node, compute the sum of its digits using the
digitSum
function. - If the sum is even, remove the current node:
- Update the
auxiliary
pointer to point to the next node. - Update the next pointer of the previous node to skip the current node.
- If the current node is the head node, update the head pointer to the next node.
- If the current node is the tail node, update the tail pointer to the previous node.
- Free the memory allocated for the removed node.
- Update the
- If the sum is odd, move the
auxiliary
pointer to the current node and continue to the next node. - Continue this process until the traversal completes and the
temp
pointer points back to the head node.
Code Solution
// Java Program
// Remove all the Even digit sum nodes from a circular linked list
class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class CircularLinkedList
{
public LinkNode head;
public LinkNode tail;
public CircularLinkedList()
{
// Set initial value
this.head = null;
this.tail = null;
}
public void insert(int value)
{
LinkNode node = new LinkNode(value);
if (this.head == null)
{
this.head = node;
}
else
{
this.tail.next = node;
}
node.next = this.head;
this.tail = node;
}
// Display node element of circular linked list
public void display()
{
if (this.head == null)
{
System.out.println("\n Empty Linked List");
}
else
{
// First node of linked list
System.out.print(" " + this.head.data);
LinkNode temp = this.head.next;
// Display linked list node
while (temp != null && temp != this.head)
{
// Display node value
System.out.print(" " + temp.data);
// visit to next node
temp = temp.next;
}
}
}
public int digitSum(int num)
{
int n = num;
int sum = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n = n / 10;
}
return sum;
}
public void removeEvenDigitSumNode()
{
if (this.head == null)
{
return;
}
LinkNode temp = this.head;
LinkNode auxiliary = this.head;
LinkNode point = null;
while (temp != null)
{
if ((digitSum(temp.data) & 1) == 0)
{
auxiliary = temp;
temp = temp.next;
if (auxiliary == this.head)
{
// Remove head node
if (auxiliary == this.tail)
{
// When Remove last node
this.tail = null;
this.head = null;
temp = null;
point = null;
}
else
{
this.head = temp;
this.tail.next = temp;
}
}
else if (auxiliary == this.tail)
{
// When Remove last node
if (point != null)
{
point.next = this.head;
}
this.tail = point;
}
else
{
// When removing intermediate node
if (point != null)
{
point.next = temp;
}
}
auxiliary = null;
}
else
{
point = temp;
// visit to next node
temp = temp.next;
if (temp == this.head)
{
// Stop the process
temp = null;
}
}
}
}
public static void main(String[] args)
{
CircularLinkedList cll = new CircularLinkedList();
// Insert node
cll.insert(13);
cll.insert(12);
cll.insert(32);
cll.insert(1);
cll.insert(14);
cll.insert(91);
cll.insert(27);
cll.insert(124);
cll.insert(88);
System.out.println("\n Before remove even digit sum nodes");
cll.display();
/*
Node Digit Sum Even
----- -------- --------
13 [1+3] 4 Yes
12 [1+2] 3 No
32 [3+2] 5 No
1 [1] 1 No
14 [1+4] 5 No
91 [9+1] 10 Yes
27 [2+7] 9 No
124 [1+2+4] 7 No
88 [8+8] 16 Yes
--------------------------
Result
------
12 → 32 → 1 → 14 → 27 → 124 ┐
└-------------------------⤶
*/
cll.removeEvenDigitSumNode();
System.out.println("\n After remove even digit sum nodes");
cll.display();
}
}
Output
Before remove even digit sum nodes
13 12 32 1 14 91 27 124 88
After remove even digit sum nodes
12 32 1 14 27 124
// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Remove all the Even digit sum nodes from a circular linked list
class LinkNode
{
public: int data;
LinkNode *next;
LinkNode(int data)
{
this->data = data;
this->next = NULL;
}
};
class CircularLinkedList
{
public: LinkNode *head;
LinkNode *tail;
CircularLinkedList()
{
this->head = NULL;
this->tail = NULL;
}
void insert(int value)
{
LinkNode *node = new LinkNode(value);
if (this->head == NULL)
{
this->head = node;
}
else
{
this->tail->next = node;
}
node->next = this->head;
this->tail = node;
}
// Display node element of circular linked list
void display()
{
if (this->head == NULL)
{
cout << "\n Empty Linked List" << endl;
}
else
{
// First node of linked list
cout << " " << this->head->data;
LinkNode *temp = this->head->next;
// Display linked list node
while (temp != NULL && temp != this->head)
{
// Display node value
cout << " " << temp->data;
// visit to next node
temp = temp->next;
}
}
}
int digitSum(int num)
{
int n = num;
int sum = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n = n / 10;
}
return sum;
}
void removeEvenDigitSumNode()
{
if (this->head == NULL)
{
return;
}
LinkNode *temp = this->head;
LinkNode *auxiliary = this->head;
LinkNode *point = NULL;
while (temp != NULL)
{
if ((this->digitSum(temp->data) &1) == 0)
{
auxiliary = temp;
temp = temp->next;
if (auxiliary == this->head)
{
// Remove head node
if (auxiliary == this->tail)
{
// When Remove last node
this->tail = NULL;
this->head = NULL;
temp = NULL;
point = NULL;
}
else
{
this->head = temp;
this->tail->next = temp;
}
}
else if (auxiliary == this->tail)
{
// When Remove last node
if (point != NULL)
{
point->next = this->head;
}
this->tail = point;
}
else
{
// When removing intermediate node
if (point != NULL)
{
point->next = temp;
}
}
delete auxiliary;
auxiliary = NULL;
}
else
{
point = temp;
// visit to next node
temp = temp->next;
if (temp == this->head)
{
// Stop the process
temp = NULL;
}
}
}
}
};
int main()
{
CircularLinkedList *cll = new CircularLinkedList();
// Insert node
cll->insert(13);
cll->insert(12);
cll->insert(32);
cll->insert(1);
cll->insert(14);
cll->insert(91);
cll->insert(27);
cll->insert(124);
cll->insert(88);
cout << "\n Before remove even digit sum nodes" << endl;
cll->display();
/*
Node Digit Sum Even
----- -------- --------
13 [1+3] 4 Yes
12 [1+2] 3 No
32 [3+2] 5 No
1 [1] 1 No
14 [1+4] 5 No
91 [9+1] 10 Yes
27 [2+7] 9 No
124 [1+2+4] 7 No
88 [8+8] 16 Yes
--------------------------
Result
------
12 → 32 → 1 → 14 → 27 → 124 ┐
└-------------------------⤶
*/
cll->removeEvenDigitSumNode();
cout << "\n After remove even digit sum nodes" << endl;
cll->display();
return 0;
}
Output
Before remove even digit sum nodes
13 12 32 1 14 91 27 124 88
After remove even digit sum nodes
12 32 1 14 27 124
// Include namespace system
using System;
// Csharp Program
// Remove all the Even digit sum nodes from a circular linked list
public class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class CircularLinkedList
{
public LinkNode head;
public LinkNode tail;
public CircularLinkedList()
{
// Set initial value
this.head = null;
this.tail = null;
}
public void insert(int value)
{
LinkNode node = new LinkNode(value);
if (this.head == null)
{
this.head = node;
}
else
{
this.tail.next = node;
}
node.next = this.head;
this.tail = node;
}
// Display node element of circular linked list
public void display()
{
if (this.head == null)
{
Console.WriteLine("\n Empty Linked List");
}
else
{
// First node of linked list
Console.Write(" " + this.head.data);
LinkNode temp = this.head.next;
// Display linked list node
while (temp != null && temp != this.head)
{
// Display node value
Console.Write(" " + temp.data);
// visit to next node
temp = temp.next;
}
}
}
public int digitSum(int num)
{
int n = num;
int sum = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n = n / 10;
}
return sum;
}
public void removeEvenDigitSumNode()
{
if (this.head == null)
{
return;
}
LinkNode temp = this.head;
LinkNode auxiliary = this.head;
LinkNode point = null;
while (temp != null)
{
if ((this.digitSum(temp.data) & 1) == 0)
{
auxiliary = temp;
temp = temp.next;
if (auxiliary == this.head)
{
// Remove head node
if (auxiliary == this.tail)
{
// When Remove last node
this.tail = null;
this.head = null;
temp = null;
point = null;
}
else
{
this.head = temp;
this.tail.next = temp;
}
}
else if (auxiliary == this.tail)
{
// When Remove last node
if (point != null)
{
point.next = this.head;
}
this.tail = point;
}
else
{
// When removing intermediate node
if (point != null)
{
point.next = temp;
}
}
auxiliary = null;
}
else
{
point = temp;
// visit to next node
temp = temp.next;
if (temp == this.head)
{
// Stop the process
temp = null;
}
}
}
}
public static void Main(String[] args)
{
CircularLinkedList cll = new CircularLinkedList();
// Insert node
cll.insert(13);
cll.insert(12);
cll.insert(32);
cll.insert(1);
cll.insert(14);
cll.insert(91);
cll.insert(27);
cll.insert(124);
cll.insert(88);
Console.WriteLine("\n Before remove even digit sum nodes");
cll.display();
/*
Node Digit Sum Even
----- -------- --------
13 [1+3] 4 Yes
12 [1+2] 3 No
32 [3+2] 5 No
1 [1] 1 No
14 [1+4] 5 No
91 [9+1] 10 Yes
27 [2+7] 9 No
124 [1+2+4] 7 No
88 [8+8] 16 Yes
--------------------------
Result
------
12 → 32 → 1 → 14 → 27 → 124 ┐
└-------------------------⤶
*/
cll.removeEvenDigitSumNode();
Console.WriteLine("\n After remove even digit sum nodes");
cll.display();
}
}
Output
Before remove even digit sum nodes
13 12 32 1 14 91 27 124 88
After remove even digit sum nodes
12 32 1 14 27 124
package main
import "fmt"
// Go Program
// Remove all the Even digit sum nodes from a circular linked list
type LinkNode struct {
data int
next * LinkNode
}
func getLinkNode(data int) * LinkNode {
var me *LinkNode = &LinkNode {}
me.data = data
me.next = nil
return me
}
type CircularLinkedList struct {
head * LinkNode
tail * LinkNode
}
func getCircularLinkedList() * CircularLinkedList {
var me *CircularLinkedList = &CircularLinkedList {}
// Set initial value
me.head = nil
me.tail = nil
return me
}
func(this *CircularLinkedList) insert(value int) {
var node * LinkNode = getLinkNode(value)
if this.head == nil {
this.head = node
} else {
this.tail.next = node
}
node.next = this.head
this.tail = node
}
// Display node element of circular linked list
func(this CircularLinkedList) display() {
if this.head == nil {
fmt.Println("\n Empty Linked List")
} else {
// First node of linked list
fmt.Print(" ", this.head.data)
var temp * LinkNode = this.head.next
// Display linked list node
for (temp != nil && temp != this.head) {
// Display node value
fmt.Print(" ", temp.data)
// visit to next node
temp = temp.next
}
}
}
func(this CircularLinkedList) digitSum(num int) int {
var n int = num
var sum int = 0
if n < 0 {
n = -n
}
for (n > 0) {
sum += (n % 10)
n = n / 10
}
return sum
}
func(this *CircularLinkedList) removeEvenDigitSumNode() {
if this.head == nil {
return
}
var temp * LinkNode = this.head
var auxiliary * LinkNode = this.head
var point * LinkNode = nil
for (temp != nil) {
if (this.digitSum(temp.data) & 1) == 0 {
auxiliary = temp
temp = temp.next
if auxiliary == this.head {
// Remove head node
if auxiliary == this.tail {
// When Remove last node
this.tail = nil
this.head = nil
temp = nil
point = nil
} else {
this.head = temp
this.tail.next = temp
}
} else if auxiliary == this.tail {
// When Remove last node
if point != nil {
point.next = this.head
}
this.tail = point
} else {
// When removing intermediate node
if point != nil {
point.next = temp
}
}
auxiliary = nil
} else {
point = temp
// visit to next node
temp = temp.next
if temp == this.head {
// Stop the process
temp = nil
}
}
}
}
func main() {
var cll * CircularLinkedList = getCircularLinkedList()
// Insert node
cll.insert(13)
cll.insert(12)
cll.insert(32)
cll.insert(1)
cll.insert(14)
cll.insert(91)
cll.insert(27)
cll.insert(124)
cll.insert(88)
fmt.Println("\n Before remove even digit sum nodes")
cll.display()
/*
Node Digit Sum Even
----- -------- --------
13 [1+3] 4 Yes
12 [1+2] 3 No
32 [3+2] 5 No
1 [1] 1 No
14 [1+4] 5 No
91 [9+1] 10 Yes
27 [2+7] 9 No
124 [1+2+4] 7 No
88 [8+8] 16 Yes
--------------------------
Result
------
12 → 32 → 1 → 14 → 27 → 124 ┐
└-------------------------⤶
*/
cll.removeEvenDigitSumNode()
fmt.Println("\n After remove even digit sum nodes")
cll.display()
}
Output
Before remove even digit sum nodes
13 12 32 1 14 91 27 124 88
After remove even digit sum nodes
12 32 1 14 27 124
<?php
// Php Program
// Remove all the Even digit sum nodes from a circular linked list
class LinkNode
{
public $data;
public $next;
public function __construct($data)
{
$this->data = $data;
$this->next = NULL;
}
}
class CircularLinkedList
{
public $head;
public $tail;
public function __construct()
{
$this->head = NULL;
$this->tail = NULL;
}
public function insert($value)
{
$node = new LinkNode($value);
if ($this->head == NULL)
{
$this->head = $node;
}
else
{
$this->tail->next = $node;
}
$node->next = $this->head;
$this->tail = $node;
}
// Display node element of circular linked list
public function display()
{
if ($this->head == NULL)
{
echo("\n Empty Linked List\n");
}
else
{
// First node of linked list
echo(" ".$this->head->data);
$temp = $this->head->next;
// Display linked list node
while ($temp != NULL && $temp != $this->head)
{
// Display node value
echo(" ".$temp->data);
// visit to next node
$temp = $temp->next;
}
}
}
public function digitSum($num)
{
$n = $num;
$sum = 0;
if ($n < 0)
{
$n = -$n;
}
while ($n > 0)
{
$sum += ($n % 10);
$n = (int)($n / 10);
}
return $sum;
}
public function removeEvenDigitSumNode()
{
if ($this->head == NULL)
{
return;
}
$temp = $this->head;
$auxiliary = $this->head;
$point = NULL;
while ($temp != NULL)
{
if (($this->digitSum($temp->data) & 1) == 0)
{
$auxiliary = $temp;
$temp = $temp->next;
if ($auxiliary == $this->head)
{
// Remove head node
if ($auxiliary == $this->tail)
{
// When Remove last node
$this->tail = NULL;
$this->head = NULL;
$temp = NULL;
$point = NULL;
}
else
{
$this->head = $temp;
$this->tail->next = $temp;
}
}
else if ($auxiliary == $this->tail)
{
// When Remove last node
if ($point != NULL)
{
$point->next = $this->head;
}
$this->tail = $point;
}
else
{
// When removing intermediate node
if ($point != NULL)
{
$point->next = $temp;
}
}
$auxiliary = NULL;
}
else
{
$point = $temp;
// visit to next node
$temp = $temp->next;
if ($temp == $this->head)
{
// Stop the process
$temp = NULL;
}
}
}
}
}
function main()
{
$cll = new CircularLinkedList();
// Insert node
$cll->insert(13);
$cll->insert(12);
$cll->insert(32);
$cll->insert(1);
$cll->insert(14);
$cll->insert(91);
$cll->insert(27);
$cll->insert(124);
$cll->insert(88);
echo("\n Before remove even digit sum nodes".
"\n");
$cll->display();
/*
Node Digit Sum Even
----- -------- --------
13 [1+3] 4 Yes
12 [1+2] 3 No
32 [3+2] 5 No
1 [1] 1 No
14 [1+4] 5 No
91 [9+1] 10 Yes
27 [2+7] 9 No
124 [1+2+4] 7 No
88 [8+8] 16 Yes
--------------------------
Result
------
12 → 32 → 1 → 14 → 27 → 124 ┐
└-------------------------⤶
*/
$cll->removeEvenDigitSumNode();
echo("\n After remove even digit sum nodes".
"\n");
$cll->display();
}
main();
Output
Before remove even digit sum nodes
13 12 32 1 14 91 27 124 88
After remove even digit sum nodes
12 32 1 14 27 124
// Node JS Program
// Remove all the Even digit sum nodes from a circular linked list
class LinkNode
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class CircularLinkedList
{
constructor()
{
this.head = null;
this.tail = null;
}
insert(value)
{
var node = new LinkNode(value);
if (this.head == null)
{
this.head = node;
}
else
{
this.tail.next = node;
}
node.next = this.head;
this.tail = node;
}
// Display node element of circular linked list
display()
{
if (this.head == null)
{
console.log("\n Empty Linked List");
}
else
{
// First node of linked list
process.stdout.write(" " + this.head.data);
var temp = this.head.next;
// Display linked list node
while (temp != null && temp != this.head)
{
// Display node value
process.stdout.write(" " + temp.data);
// visit to next node
temp = temp.next;
}
}
}
digitSum(num)
{
var n = num;
var sum = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n = parseInt(n / 10);
}
return sum;
}
removeEvenDigitSumNode()
{
if (this.head == null)
{
return;
}
var temp = this.head;
var auxiliary = this.head;
var point = null;
while (temp != null)
{
if ((this.digitSum(temp.data) & 1) == 0)
{
auxiliary = temp;
temp = temp.next;
if (auxiliary == this.head)
{
// Remove head node
if (auxiliary == this.tail)
{
// When Remove last node
this.tail = null;
this.head = null;
temp = null;
point = null;
}
else
{
this.head = temp;
this.tail.next = temp;
}
}
else if (auxiliary == this.tail)
{
// When Remove last node
if (point != null)
{
point.next = this.head;
}
this.tail = point;
}
else
{
// When removing intermediate node
if (point != null)
{
point.next = temp;
}
}
auxiliary = null;
}
else
{
point = temp;
// visit to next node
temp = temp.next;
if (temp == this.head)
{
// Stop the process
temp = null;
}
}
}
}
}
function main()
{
var cll = new CircularLinkedList();
// Insert node
cll.insert(13);
cll.insert(12);
cll.insert(32);
cll.insert(1);
cll.insert(14);
cll.insert(91);
cll.insert(27);
cll.insert(124);
cll.insert(88);
console.log("\n Before remove even digit sum nodes");
cll.display();
/*
Node Digit Sum Even
----- -------- --------
13 [1+3] 4 Yes
12 [1+2] 3 No
32 [3+2] 5 No
1 [1] 1 No
14 [1+4] 5 No
91 [9+1] 10 Yes
27 [2+7] 9 No
124 [1+2+4] 7 No
88 [8+8] 16 Yes
--------------------------
Result
------
12 → 32 → 1 → 14 → 27 → 124 ┐
└-------------------------⤶
*/
cll.removeEvenDigitSumNode();
console.log("\n After remove even digit sum nodes");
cll.display();
}
main();
Output
Before remove even digit sum nodes
13 12 32 1 14 91 27 124 88
After remove even digit sum nodes
12 32 1 14 27 124
# Python 3 Program
# Remove all the Even digit sum nodes from a circular linked list
class LinkNode :
def __init__(self, data) :
self.data = data
self.next = None
class CircularLinkedList :
def __init__(self) :
self.head = None
self.tail = None
def insert(self, value) :
node = LinkNode(value)
if (self.head == None) :
self.head = node
else :
self.tail.next = node
node.next = self.head
self.tail = node
# Display node element of circular linked list
def display(self) :
if (self.head == None) :
print("\n Empty Linked List")
else :
# First node of linked list
print(" ", self.head.data, end = "")
temp = self.head.next
# Display linked list node
while (temp != None and temp != self.head) :
# Display node value
print(" ", temp.data, end = "")
# visit to next node
temp = temp.next
def digitSum(self, num) :
n = num
sum = 0
if (n < 0) :
n = -n
while (n > 0) :
sum += (n % 10)
n = int(n / 10)
return sum
def removeEvenDigitSumNode(self) :
if (self.head == None) :
return
temp = self.head
auxiliary = self.head
point = None
while (temp != None) :
if ((self.digitSum(temp.data) & 1) == 0) :
auxiliary = temp
temp = temp.next
if (auxiliary == self.head) :
# Remove head node
if (auxiliary == self.tail) :
# When Remove last node
self.tail = None
self.head = None
temp = None
point = None
else :
self.head = temp
self.tail.next = temp
elif (auxiliary == self.tail) :
# When Remove last node
if (point != None) :
point.next = self.head
self.tail = point
else :
# When removing intermediate node
if (point != None) :
point.next = temp
auxiliary = None
else :
point = temp
# visit to next node
temp = temp.next
if (temp == self.head) :
# Stop the process
temp = None
def main() :
cll = CircularLinkedList()
# Insert node
cll.insert(13)
cll.insert(12)
cll.insert(32)
cll.insert(1)
cll.insert(14)
cll.insert(91)
cll.insert(27)
cll.insert(124)
cll.insert(88)
print("\n Before remove even digit sum nodes")
cll.display()
# Node Digit Sum Even
# ----- -------- --------
# 13 [1+3] 4 Yes
# 12 [1+2] 3 No
# 32 [3+2] 5 No
# 1 [1] 1 No
# 14 [1+4] 5 No
# 91 [9+1] 10 Yes
# 27 [2+7] 9 No
# 124 [1+2+4] 7 No
# 88 [8+8] 16 Yes
# --------------------------
# Result
# ------
# 12 → 32 → 1 → 14 → 27 → 124 ┐
# └-------------------------⤶
cll.removeEvenDigitSumNode()
print("\n After remove even digit sum nodes")
cll.display()
if __name__ == "__main__": main()
Output
Before remove even digit sum nodes
13 12 32 1 14 91 27 124 88
After remove even digit sum nodes
12 32 1 14 27 124
# Ruby Program
# Remove all the Even digit sum nodes from a circular linked list
class LinkNode
# Define the accessor and reader of class LinkNode
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end
class CircularLinkedList
# Define the accessor and reader of class CircularLinkedList
attr_reader :head, :tail
attr_accessor :head, :tail
def initialize()
self.head = nil
self.tail = nil
end
def insert(value)
node = LinkNode.new(value)
if (self.head == nil)
self.head = node
else
self.tail.next = node
end
node.next = self.head
self.tail = node
end
# Display node element of circular linked list
def display()
if (self.head == nil)
print("\n Empty Linked List", "\n")
else
# First node of linked list
print(" ", self.head.data)
temp = self.head.next
# Display linked list node
while (temp != nil && temp != self.head)
# Display node value
print(" ", temp.data)
# visit to next node
temp = temp.next
end
end
end
def digitSum(num)
n = num
sum = 0
if (n < 0)
n = -n
end
while (n > 0)
sum += (n % 10)
n = n / 10
end
return sum
end
def removeEvenDigitSumNode()
if (self.head == nil)
return
end
temp = self.head
auxiliary = self.head
point = nil
while (temp != nil)
if ((self.digitSum(temp.data) & 1) == 0)
auxiliary = temp
temp = temp.next
if (auxiliary == self.head)
# Remove head node
if (auxiliary == self.tail)
# When Remove last node
self.tail = nil
self.head = nil
temp = nil
point = nil
else
self.head = temp
self.tail.next = temp
end
elsif (auxiliary == self.tail)
# When Remove last node
if (point != nil)
point.next = self.head
end
self.tail = point
else
# When removing intermediate node
if (point != nil)
point.next = temp
end
end
auxiliary = nil
else
point = temp
# visit to next node
temp = temp.next
if (temp == self.head)
# Stop the process
temp = nil
end
end
end
end
end
def main()
cll = CircularLinkedList.new()
# Insert node
cll.insert(13)
cll.insert(12)
cll.insert(32)
cll.insert(1)
cll.insert(14)
cll.insert(91)
cll.insert(27)
cll.insert(124)
cll.insert(88)
print("\n Before remove even digit sum nodes", "\n")
cll.display()
# Node Digit Sum Even
# ----- -------- --------
# 13 [1+3] 4 Yes
# 12 [1+2] 3 No
# 32 [3+2] 5 No
# 1 [1] 1 No
# 14 [1+4] 5 No
# 91 [9+1] 10 Yes
# 27 [2+7] 9 No
# 124 [1+2+4] 7 No
# 88 [8+8] 16 Yes
# --------------------------
# Result
# ------
# 12 → 32 → 1 → 14 → 27 → 124 ┐
# └-------------------------⤶
cll.removeEvenDigitSumNode()
print("\n After remove even digit sum nodes", "\n")
cll.display()
end
main()
Output
Before remove even digit sum nodes
13 12 32 1 14 91 27 124 88
After remove even digit sum nodes
12 32 1 14 27 124
// Scala Program
// Remove all the Even digit sum nodes from a circular linked list
class LinkNode(var data: Int,
var next: LinkNode)
{
def this(data: Int)
{
this(data, null);
}
}
class CircularLinkedList(var head: LinkNode,
var tail: LinkNode)
{
def this()
{
this(null, null);
}
def insert(value: Int): Unit = {
var node: LinkNode = new LinkNode(value);
if (this.head == null)
{
this.head = node;
}
else
{
this.tail.next = node;
}
node.next = this.head;
this.tail = node;
}
// Display node element of circular linked list
def display(): Unit = {
if (this.head == null)
{
println("\n Empty Linked List");
}
else
{
// First node of linked list
print(" " + this.head.data);
var temp: LinkNode = this.head.next;
// Display linked list node
while (temp != null && temp != this.head)
{
// Display node value
print(" " + temp.data);
// visit to next node
temp = temp.next;
}
}
}
def digitSum(num: Int): Int = {
var n: Int = num;
var sum: Int = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n = n / 10;
}
return sum;
}
def removeEvenDigitSumNode(): Unit = {
if (this.head == null)
{
return;
}
var temp: LinkNode = this.head;
var auxiliary: LinkNode = this.head;
var point: LinkNode = null;
while (temp != null)
{
if ((digitSum(temp.data) & 1) == 0)
{
auxiliary = temp;
temp = temp.next;
if (auxiliary == this.head)
{
// Remove head node
if (auxiliary == this.tail)
{
// When Remove last node
this.tail = null;
this.head = null;
temp = null;
point = null;
}
else
{
this.head = temp;
this.tail.next = temp;
}
}
else if (auxiliary == this.tail)
{
// When Remove last node
if (point != null)
{
point.next = this.head;
}
this.tail = point;
}
else
{
// When removing intermediate node
if (point != null)
{
point.next = temp;
}
}
auxiliary = null;
}
else
{
point = temp;
// visit to next node
temp = temp.next;
if (temp == this.head)
{
// Stop the process
temp = null;
}
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var cll: CircularLinkedList = new CircularLinkedList();
// Insert node
cll.insert(13);
cll.insert(12);
cll.insert(32);
cll.insert(1);
cll.insert(14);
cll.insert(91);
cll.insert(27);
cll.insert(124);
cll.insert(88);
println("\n Before remove even digit sum nodes");
cll.display();
/*
Node Digit Sum Even
----- -------- --------
13 [1+3] 4 Yes
12 [1+2] 3 No
32 [3+2] 5 No
1 [1] 1 No
14 [1+4] 5 No
91 [9+1] 10 Yes
27 [2+7] 9 No
124 [1+2+4] 7 No
88 [8+8] 16 Yes
--------------------------
Result
------
12 → 32 → 1 → 14 → 27 → 124 ┐
└-------------------------⤶
*/
cll.removeEvenDigitSumNode();
println("\n After remove even digit sum nodes");
cll.display();
}
}
Output
Before remove even digit sum nodes
13 12 32 1 14 91 27 124 88
After remove even digit sum nodes
12 32 1 14 27 124
// Swift 4 Program
// Remove all the Even digit sum nodes from a circular linked list
class LinkNode
{
var data: Int;
var next: LinkNode? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class CircularLinkedList
{
var head: LinkNode? ;
var tail: LinkNode? ;
init()
{
self.head = nil;
self.tail = nil;
}
func insert(_ value: Int)
{
let node: LinkNode = LinkNode(value);
if (self.head == nil)
{
self.head = node;
}
else
{
self.tail!.next = node;
}
node.next = self.head;
self.tail = node;
}
// Display node element of circular linked list
func display()
{
if (self.head == nil)
{
print("\n Empty Linked List");
}
else
{
// First node of linked list
print(" ", self.head!.data, terminator: "");
var temp: LinkNode? = self.head!.next;
// Display linked list node
while (temp != nil && !(temp === self.head))
{
// Display node value
print(" ", temp!.data, terminator: "");
// visit to next node
temp = temp!.next;
}
}
}
func digitSum(_ num: Int) -> Int
{
var n: Int = num;
var sum: Int = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n = n / 10;
}
return sum;
}
func removeEvenDigitSumNode()
{
if (self.head == nil)
{
return;
}
var temp: LinkNode? = self.head;
var auxiliary: LinkNode? = self.head;
var point: LinkNode? = nil;
while (temp != nil)
{
if ((self.digitSum(temp!.data) & 1) == 0)
{
auxiliary = temp;
temp = temp!.next;
if (auxiliary === self.head)
{
// Remove head node
if (auxiliary === self.tail)
{
// When Remove last node
self.tail = nil;
self.head = nil;
temp = nil;
point = nil;
}
else
{
self.head = temp;
self.tail!.next = temp;
}
}
else if (auxiliary === self.tail)
{
// When Remove last node
if (point != nil)
{
point!.next = self.head;
}
self.tail = point;
}
else
{
// When removing intermediate node
if (point != nil)
{
point!.next = temp;
}
}
auxiliary = nil;
}
else
{
point = temp;
// visit to next node
temp = temp!.next;
if (temp === self.head)
{
// Stop the process
temp = nil;
}
}
}
}
}
func main()
{
let cll: CircularLinkedList = CircularLinkedList();
// Insert node
cll.insert(13);
cll.insert(12);
cll.insert(32);
cll.insert(1);
cll.insert(14);
cll.insert(91);
cll.insert(27);
cll.insert(124);
cll.insert(88);
print("\n Before remove even digit sum nodes");
cll.display();
/*
Node Digit Sum Even
----- -------- --------
13 [1+3] 4 Yes
12 [1+2] 3 No
32 [3+2] 5 No
1 [1] 1 No
14 [1+4] 5 No
91 [9+1] 10 Yes
27 [2+7] 9 No
124 [1+2+4] 7 No
88 [8+8] 16 Yes
--------------------------
Result
------
12 → 32 → 1 → 14 → 27 → 124 ┐
└-------------------------⤶
*/
cll.removeEvenDigitSumNode();
print("\n After remove even digit sum nodes");
cll.display();
}
main();
Output
Before remove even digit sum nodes
13 12 32 1 14 91 27 124 88
After remove even digit sum nodes
12 32 1 14 27 124
// Kotlin Program
// Remove all the Even digit sum nodes from a circular linked list
class LinkNode
{
var data: Int;
var next: LinkNode ? ;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class CircularLinkedList
{
var head: LinkNode ? ;
var tail: LinkNode ? ;
constructor()
{
this.head = null;
this.tail = null;
}
fun insert(value: Int): Unit
{
val node: LinkNode = LinkNode(value);
if (this.head == null)
{
this.head = node;
}
else
{
this.tail?.next = node;
}
node.next = this.head;
this.tail = node;
}
// Display node element of circular linked list
fun display(): Unit
{
if (this.head == null)
{
println("\n Empty Linked List");
}
else
{
// First node of linked list
print(" " + this.head?.data);
var temp: LinkNode ? = this.head?.next;
// Display linked list node
while (temp != null && temp != this.head)
{
// Display node value
print(" " + temp.data);
// visit to next node
temp = temp.next;
}
}
}
fun digitSum(num: Int): Int
{
var n: Int = num;
var sum: Int = 0;
if (n < 0)
{
n = -n;
}
while (n > 0)
{
sum += (n % 10);
n = n / 10;
}
return sum;
}
fun removeEvenDigitSumNode(): Unit
{
if (this.head == null)
{
return;
}
var temp: LinkNode ? = this.head;
var auxiliary: LinkNode ? ;
var point: LinkNode ? = null;
while (temp != null)
{
if ((this.digitSum(temp.data) and 1) == 0)
{
auxiliary = temp;
temp = temp.next;
if (auxiliary == this.head)
{
// Remove head node
if (auxiliary == this.tail)
{
// When Remove last node
this.tail = null;
this.head = null;
temp = null;
point = null;
}
else
{
this.head = temp;
this.tail?.next = temp;
}
}
else if (auxiliary == this.tail)
{
// When Remove last node
if (point != null)
{
point.next = this.head;
}
this.tail = point;
}
else
{
// When removing intermediate node
if (point != null)
{
point.next = temp;
}
}
}
else
{
point = temp;
// visit to next node
temp = temp.next;
if (temp == this.head)
{
// Stop the process
temp = null;
}
}
}
}
}
fun main(args: Array < String > ): Unit
{
val cll: CircularLinkedList = CircularLinkedList();
// Insert node
cll.insert(13);
cll.insert(12);
cll.insert(32);
cll.insert(1);
cll.insert(14);
cll.insert(91);
cll.insert(27);
cll.insert(124);
cll.insert(88);
println("\n Before remove even digit sum nodes");
cll.display();
/*
Node Digit Sum Even
----- -------- --------
13 [1+3] 4 Yes
12 [1+2] 3 No
32 [3+2] 5 No
1 [1] 1 No
14 [1+4] 5 No
91 [9+1] 10 Yes
27 [2+7] 9 No
124 [1+2+4] 7 No
88 [8+8] 16 Yes
--------------------------
Result
------
12 → 32 → 1 → 14 → 27 → 124 ┐
└-------------------------⤶
*/
cll.removeEvenDigitSumNode();
println("\n After remove even digit sum nodes");
cll.display();
}
Output
Before remove even digit sum nodes
13 12 32 1 14 91 27 124 88
After remove even digit sum nodes
12 32 1 14 27 124
Time Complexity
The time complexity of removing nodes with even digit sums from a circular linked list is O(n), where n is the number of nodes in the linked list. In the worst case, the algorithm may need to traverse all nodes in the circular linked list to determine whether the digit sum is even or odd.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment