Posted on by Kalkicode
Code Circular Linked List

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:

  1. Initialize pointers temp and auxiliary to the head node of the circular linked list.
  2. Traverse the circular linked list using the temp pointer.
  3. For each node, compute the sum of its digits using the digitSum function.
  4. 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.
  5. If the sum is odd, move the auxiliary pointer to the current node and continue to the next node.
  6. 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

  1. If the circular linked list is empty, return.
  2. Initialize pointers temp and auxiliary to the head node of the circular linked list. Also, initialize point to null.
  3. Traverse the circular linked list using the temp pointer.
  4. For each node, compute the sum of its digits using the digitSum function.
  5. 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.
  6. If the sum is odd, move the auxiliary pointer to the current node and continue to the next node.
  7. 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.

Comment

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





Categories
Relative Post