Data Structures - Circular Singly Linked List Other Related Topics
Data Structures - Circular Singly Linked List Other Related Topics

Circular Singly Linked List - Delete odd nodes

Deleting odd nodes of a circular singly linked list requires traverse through the list and deleting odd nodes one by one. It involves the following process. If the list contains only head then make the head null. If the list contains more than one element then delete the head and adjust the link of last element with the new head. If next of head is not head then, create three nodes - evenNode pointing to head, oddNode pointing to next of head and temp to store last even node. Then delete oddNode and update evenNode and oddNode to next set of odd-even nodes and continue the process till any of the node reaches head. After that if evenNode reaches head, make next of temp as head else make next of evenNode as head.

The function deleteOddNodes is created for this purpose. It is a 5-step process.

void deleteOddNodes() {
  //1. if head is the only element element in 
  //   list make the head as null  
  if(head != NULL && head->next == head) {
    free(head);
    head = NULL;
  } else if(head != NULL) {

    //2. if the list contains more than one element
    //   delete the head and adjust the link of
    //   last element with the new head       
    Node* temp = head;
    while(temp->next != head) {
      temp = temp->next;
    }
    temp->next = head->next;
    free(head);
    head = temp->next;

    //3. create evenNode node - pointing to head
    //   oddNode node - pointing to next of head
    //   temp node - to store last even node
    if(head != NULL && head->next != head) {

      Node* evenNode = head;
      Node* oddNode = head->next; 
      while(true) {
        
        //4. delete odd node and update evenNode and 
        //   oddNode to next set of odd-even nodes update
        //   temp node to latest evenNode node continue
        //   the process till any of the node reaches head
        temp = evenNode;
        evenNode->next = oddNode->next;
        free(oddNode);
        evenNode = evenNode->next;
        oddNode = evenNode->next;
        if(evenNode == head || oddNode == head)
          break;
      }
      
      //5. if evenNode reaches head, make next of temp
      //   as head else make next of evenNode as head
      if(evenNode == head)
        temp->next = head;
      else
        evenNode->next = head;
    }
  } 
}

void deleteOddNodes(struct Node** head_ref) {
  //1. if head is the only element element in 
  //   list make the head as null  
  if(*head_ref != NULL && (*head_ref)->next == *head_ref) {
    free(*head_ref);
    *head_ref = NULL;
  } else if(*head_ref != NULL) {

    //2. if the list contains more than one element
    //   delete the head and adjust the link of
    //   last element with the new head       
    struct Node* temp = *head_ref;
    while(temp->next != *head_ref) {
      temp = temp->next;
    }
    temp->next = (*head_ref)->next;
    free(*head_ref);
    *head_ref = temp->next;

    //3. create evenNode node - pointing to head
    //   oddNode node - pointing to next of head
    //   temp node - to store last even node
    if(*head_ref != NULL && (*head_ref)->next != *head_ref) {

      struct Node* evenNode = *head_ref;
      struct Node* oddNode = (*head_ref)->next; 
      while(1) {
        
        //4. delete odd node and update evenNode and 
        //   oddNode to next set of odd-even nodes update
        //   temp node to latest evenNode node continue
        //   the process till any of the node reaches head
        temp = evenNode;
        evenNode->next = oddNode->next;
        free(oddNode);
        evenNode = evenNode->next;
        oddNode = evenNode->next;
        if(evenNode == *head_ref || oddNode == *head_ref)
          break;
      }
      
      //5. if evenNode reaches head, make next of temp
      //   as head else make next of evenNode as head
      if(evenNode == *head_ref)
        temp->next = *head_ref;
      else
        evenNode->next = *head_ref;
    }
  } 
}

def deleteOddNodes(self):  
  #1. if head is the only element element in 
  #   list make the head as null  
  if(self.head != None and self.head.next == self.head):
    self.head = None
  elif (self.head != None):

    #2. if the list contains more than one element
    #   delete the head and adjust the link of
    #   last element with the new head       
    temp = self.head
    while(temp.next != self.head):
      temp = temp.next
    temp.next = self.head.next
    self.head = None
    self.head = temp.next

    #3. create evenNode node - pointing to head
    #   oddNode node - pointing to next of head
    #   temp node - to store last even node
    if(self.head != None and self.head.next != self.head):

      evenNode = self.head
      oddNode = self.head.next
      while(True):
        
        #4. delete odd node and update evenNode and 
        #   oddNode to next set of odd-even nodes update
        #   temp node to latest evenNode node continue
        #   the process till any of the node reaches head
        temp = evenNode
        evenNode.next = oddNode.next
        oddNode = None
        evenNode = evenNode.next
        oddNode = evenNode.next
        if(evenNode == self.head or oddNode == self.head):
          break
      
      #5. if evenNode reaches head, make next of temp
      #   as head else make next of evenNode as head
      if(evenNode == self.head):
        temp.next = self.head
      else:
        evenNode.next = self.head

void deleteOddNodes() {
  //1. if head is the only element element in 
  //   list make the head as null  
  if(this.head != null && this.head.next == this.head) {
    this.head = null;
  } else if(this.head != null) {

    //2. if the list contains more than one element
    //   delete the head and adjust the link of
    //   last element with the new head       
    Node temp = this.head;
    while(temp.next != this.head) {
      temp = temp.next;
    }
    temp.next = head.next;
    this.head = null;
    this.head = temp.next;

    //3. create evenNode node - pointing to head
    //   oddNode node - pointing to next of head
    //   temp node - to store last even node
    if(this.head != null && this.head.next != this.head) {

      Node evenNode = this.head;
      Node oddNode = this.head.next; 
      while(true) {
        
        //4. delete odd node and update evenNode and 
        //   oddNode to next set of odd-even nodes update
        //   temp node to latest evenNode node continue
        //   the process till any of the node reaches head
        temp = evenNode;
        evenNode.next = oddNode.next;
        oddNode = null;
        evenNode = evenNode.next;
        oddNode = evenNode.next;
        if(evenNode == this.head || oddNode == this.head)
          break;
      }
      
      //5. if evenNode reaches head, make next of temp
      //   as head else make next of evenNode as head
      if(evenNode == this.head)
        temp.next = this.head;
      else
        evenNode.next = this.head;
    }
  } 
}

public void deleteOddNodes() {
  //1. if head is the only element element in 
  //   list make the head as null  
  if(this.head != null && this.head.next == this.head) {
    this.head = null;
  } else if(this.head != null) {

    //2. if the list contains more than one element
    //   delete the head and adjust the link of
    //   last element with the new head       
    Node temp = this.head;
    while(temp.next != this.head) {
      temp = temp.next;
    }
    temp.next = head.next;
    this.head = null;
    this.head = temp.next;

    //3. create evenNode node - pointing to head
    //   oddNode node - pointing to next of head
    //   temp node - to store last even node
    if(this.head != null && this.head.next != this.head) {

      Node evenNode = this.head;
      Node oddNode = this.head.next; 
      while(true) {
        
        //4. delete odd node and update evenNode and 
        //   oddNode to next set of odd-even nodes update
        //   temp node to latest evenNode node continue
        //   the process till any of the node reaches head
        temp = evenNode;
        evenNode.next = oddNode.next;
        oddNode = null;
        evenNode = evenNode.next;
        oddNode = evenNode.next;
        if(evenNode == this.head || oddNode == this.head)
          break;
      }
      
      //5. if evenNode reaches head, make next of temp
      //   as head else make next of evenNode as head
      if(evenNode == this.head)
        temp.next = this.head;
      else
        evenNode.next = this.head;
    }
  } 
}    

public function deleteOddNodes() {
  //1. if head is the only element element in 
  //   list make the head as null  
  if($this->head != null && $this->head->next == $this->head) {
    $this->head = null;
  } else if($this->head != null) {

    //2. if the list contains more than one element
    //   delete the head and adjust the link of
    //   last element with the new head       
    $temp = $this->head;
    while($temp->next != $this->head) {
      $temp = $temp->next;
    }
    $temp->next = $this->head->next;
    $this->head = null;
    $this->head = $temp->next;

    //3. create evenNode node - pointing to head
    //   oddNode node - pointing to next of head
    //   temp node - to store last even node
    if($this->head != null && $this->head->next != $this->head) {

      $evenNode = $this->head;
      $oddNode = $this->head->next; 
      while(true) {
        
        //4. delete odd node and update evenNode and 
        //   oddNode to next set of odd-even nodes update
        //   temp node to latest evenNode node continue
        //   the process till any of the node reaches head
        $temp = $evenNode;
        $evenNode->next = $oddNode->next;
        $oddNode = null;
        $evenNode = $evenNode->next;
        $oddNode = $evenNode->next;
        if($evenNode == $this->head || $oddNode == $this->head)
          break;
      }
      
      //5. if evenNode reaches head, make next of temp
      //   as head else make next of evenNode as head
      if($evenNode == $this->head)
        $temp->next = $this->head;
      else
        $evenNode->next = $this->head;
    }
  } 
}

The below is a complete program that uses above discussed concept of deleting odd nodes of a circular singly linked list.

#include <iostream>
using namespace std;

//node structure
struct Node {
    int data;
    Node* next;
};

class LinkedList {
  private:
    Node* head;
  public:
    LinkedList(){
      head = NULL;
    }
 
    //Add new element at the end of the list
    void push_back(int newElement) {
      Node* newNode = new Node();
      newNode->data = newElement;
      newNode->next = NULL; 
      if(head == NULL) {
        head = newNode;
        newNode->next = head;
      } else {
        Node* temp = head;
        while(temp->next != head)
          temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
      }    
    }

    //delete odd nodes of the list
    void deleteOddNodes() {
      if(head != NULL && head->next == head) {
        free(head);
        head = NULL;
      } else if(head != NULL) {
     
        Node* temp = head;
        while(temp->next != head) {
          temp = temp->next;
        }
        temp->next = head->next;
        free(head);
        head = temp->next;

        if(head != NULL && head->next != head) {

          Node* evenNode = head;
          Node* oddNode = head->next; 
          while(true) {
            temp = evenNode;
            evenNode->next = oddNode->next;
            free(oddNode);
            evenNode = evenNode->next;
            oddNode = evenNode->next;
            if(evenNode == head || oddNode == head)
              break;
          }
          
          if(evenNode == head)
            temp->next = head;
          else
            evenNode->next = head;
        }
      } 
    }

    //display the content of the list
    void PrintList() {
      Node* temp = head;
      if(temp != NULL) {
        cout<<"The list contains: ";
        while(true) {
          cout<<temp->data<<" ";
          temp = temp->next;
          if(temp == head) 
            break;
        }
        cout<<endl;
      } else {
        cout<<"The list is empty.\n";
      }
    }     
};

// test the code 
int main() {
  LinkedList MyList;

  //Add five elements in the list.
  MyList.push_back(10);
  MyList.push_back(20);
  MyList.push_back(30);
  MyList.push_back(40);
  MyList.push_back(50);

  //Display the content of the list.
  MyList.PrintList();

  //delete odd nodes of the list
  MyList.deleteOddNodes();

  cout<<"After deleting odd nodes:\n";
  //Display the content of the list.
  MyList.PrintList();
  
  return 0; 
}

The above code will give the following output: 

The list contains: 10 20 30 40 50 
After deleting odd nodes:
The list contains: 20 40 

#include <stdio.h>
#include <stdlib.h>

//node structure
struct Node {
  int data;
  struct Node* next;
};

//Add new element at the end of the list
void push_back(struct Node** head_ref, int newElement) {  
  struct Node *newNode, *temp;
  newNode = (struct Node*)malloc(sizeof(struct Node)); 
  newNode->data = newElement;  
  newNode->next = NULL;
  if(*head_ref == NULL) {
    *head_ref = newNode;
     newNode->next = *head_ref;
  } else {
    temp = *head_ref;
    while(temp->next != *head_ref) {
      temp = temp->next;
    }    
    temp->next = newNode;
    newNode->next = *head_ref;
  }
}

//delete odd nodes of the list
void deleteOddNodes(struct Node** head_ref) {
  if(*head_ref != NULL && (*head_ref)->next == *head_ref) {
    free(*head_ref);
    *head_ref = NULL;
  } else if(*head_ref != NULL) {
     
    struct Node* temp = *head_ref;
    while(temp->next != *head_ref) {
      temp = temp->next;
    }
    temp->next = (*head_ref)->next;
    free(*head_ref);
    *head_ref = temp->next;

    if(*head_ref != NULL && (*head_ref)->next != *head_ref) {

      struct Node* evenNode = *head_ref;
      struct Node* oddNode = (*head_ref)->next; 
      while(1) {
        temp = evenNode;
        evenNode->next = oddNode->next;
        free(oddNode);
        evenNode = evenNode->next;
        oddNode = evenNode->next;
        if(evenNode == *head_ref || oddNode == *head_ref)
          break;
      }
      
      if(evenNode == *head_ref)
        temp->next = *head_ref;
      else
        evenNode->next = *head_ref;
    }
  } 
}

//display the content of the list
void PrintList(struct Node* head_ref) {
  struct Node* temp = head_ref;
  if(head_ref != NULL) {
    printf("The list contains: ");
    while (1) {
      printf("%i ",temp->data);
      temp = temp->next;
      if(temp == head_ref)
        break;    
    }
    printf("\n");
  } else {
    printf("The list is empty.\n");
  }   
}

// test the code 
int main() {
  struct Node* MyList = NULL;

  //Add five elements in the list.
  push_back(&MyList, 10);
  push_back(&MyList, 20);
  push_back(&MyList, 30);
  push_back(&MyList, 40);
  push_back(&MyList, 50);

  //Display the content of the list.
  PrintList(MyList);

  //delete odd nodes of the list
  deleteOddNodes(&MyList);

  printf("After deleting odd nodes:\n");
  //Display the content of the list.
  PrintList(MyList);

  return 0; 
}

The above code will give the following output: 

The list contains: 10 20 30 40 50 
After deleting odd nodes:
The list contains: 20 40 

# node structure
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

#class Linked List
class LinkedList:
  def __init__(self):
    self.head = None

  #Add new element at the end of the list
  def push_back(self, newElement):
    newNode = Node(newElement)
    if(self.head == None):
      self.head = newNode
      newNode.next = self.head
      return
    else:
      temp = self.head
      while(temp.next != self.head):
        temp = temp.next
      temp.next = newNode
      newNode.next = self.head

  #delete odd nodes of the list
  def deleteOddNodes(self):  
    if(self.head != None and self.head.next == self.head):
      self.head = None
    elif (self.head != None):
     
      temp = self.head
      while(temp.next != self.head):
        temp = temp.next
      temp.next = self.head.next
      self.head = None
      self.head = temp.next

      if(self.head != None and self.head.next != self.head):

        evenNode = self.head
        oddNode = self.head.next
        while(True):
          temp = evenNode
          evenNode.next = oddNode.next
          oddNode = None
          evenNode = evenNode.next
          oddNode = evenNode.next
          if(evenNode == self.head or oddNode == self.head):
            break
        
        if(evenNode == self.head):
          temp.next = self.head
        else:
          evenNode.next = self.head

  #display the content of the list
  def PrintList(self):
    temp = self.head
    if(temp != None):
      print("The list contains:", end=" ")
      while (True):
        print(temp.data, end=" ")
        temp = temp.next
        if(temp == self.head):
          break
      print()
    else:
      print("The list is empty.")

# test the code                  
MyList = LinkedList()

#Add five elements in the list.
MyList.push_back(10)
MyList.push_back(20)
MyList.push_back(30)
MyList.push_back(40)
MyList.push_back(50)

#Display the content of the list.
MyList.PrintList()

#delete odd nodes of the list
MyList.deleteOddNodes()

print("After deleting odd nodes:")
#Display the content of the list.
MyList.PrintList()

The above code will give the following output: 

The list contains: 10 20 30 40 50 
After deleting odd nodes:
The list contains: 20 40 

//node structure
class Node {
    int data;
    Node next;
};

class LinkedList {
  Node head;

  LinkedList(){
    head = null;
  }

  //Add new element at the end of the list
  void push_back(int newElement) {
    Node newNode = new Node();
    newNode.data = newElement;
    newNode.next = null; 
    if(head == null) {
      head = newNode;
      newNode.next = head;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != head)
        temp = temp.next;
      temp.next = newNode;
      newNode.next = head;
    }    
  }

  //delete odd nodes of the list
  void deleteOddNodes() {
    if(this.head != null && this.head.next == this.head) {
      this.head = null;
    } else if(this.head != null) {    
      Node temp = this.head;
      while(temp.next != this.head) {
        temp = temp.next;
      }
      temp.next = head.next;
      this.head = null;
      this.head = temp.next;

      if(this.head != null && this.head.next != this.head) {

        Node evenNode = this.head;
        Node oddNode = this.head.next; 
        while(true) {
          temp = evenNode;
          evenNode.next = oddNode.next;
          oddNode = null;
          evenNode = evenNode.next;
          oddNode = evenNode.next;
          if(evenNode == this.head || oddNode == this.head)
            break;
        }
        
        if(evenNode == this.head)
          temp.next = this.head;
        else
          evenNode.next = this.head;
      }
    } 
  }   

  //display the content of the list
  void PrintList() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      System.out.print("The list contains: ");
      while(true) {
        System.out.print(temp.data + " ");
        temp = temp.next;
        if(temp == this.head)
          break;
      }
      System.out.println();
    } else {
      System.out.println("The list is empty.");
    }
  }     
};

// test the code 
public class Implementation {
  public static void main(String[] args) {
    LinkedList MyList = new LinkedList();

    //Add five elements in the list.
    MyList.push_back(10);
    MyList.push_back(20);
    MyList.push_back(30);
    MyList.push_back(40);
    MyList.push_back(50);

    //Display the content of the list.
    MyList.PrintList();

    //delete odd nodes of the list
    MyList.deleteOddNodes();
 
    System.out.println("After deleting odd nodes:");
    //Display the content of the list.
    MyList.PrintList();
  }
}

The above code will give the following output: 

The list contains: 10 20 30 40 50 
After deleting odd nodes:
The list contains: 20 40 

using System;

//node structure
class Node {
  public int data;
  public Node next;
};

class LinkedList {
  Node head;

  public LinkedList(){
    head = null;
  }
  
  //Add new element at the end of the list
  public void push_back(int newElement) {
    Node newNode = new Node();
    newNode.data = newElement;
    newNode.next = null; 
    if(head == null) {
      head = newNode;
      newNode.next = head;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != head)
        temp = temp.next;
      temp.next = newNode;
      newNode.next = head;
    }    
  }

  //delete odd nodes of the list
  public void deleteOddNodes() {
    if(this.head != null && this.head.next == this.head) {
      this.head = null;
    } else if(this.head != null) {
     
      Node temp = this.head;
      while(temp.next != this.head) {
        temp = temp.next;
      }
      temp.next = head.next;
      this.head = null;
      this.head = temp.next;

      if(this.head != null && this.head.next != this.head) {

        Node evenNode = this.head;
        Node oddNode = this.head.next; 
        while(true) {
          temp = evenNode;
          evenNode.next = oddNode.next;
          oddNode = null;
          evenNode = evenNode.next;
          oddNode = evenNode.next;
          if(evenNode == this.head || oddNode == this.head)
            break;
        }

        if(evenNode == this.head)
          temp.next = this.head;
        else
          evenNode.next = this.head;
      }
    } 
  }    

  //display the content of the list
  public void PrintList() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      Console.Write("The list contains: ");
      while(true) {
        Console.Write(temp.data + " ");
        temp = temp.next;
        if(temp == this.head)
          break;        
      }
      Console.WriteLine();
    } else {
      Console.WriteLine("The list is empty.");
    }
  }      
};

// test the code
class Implementation {  
  static void Main(string[] args) {
    LinkedList MyList = new LinkedList();

    //Add five elements in the list.
    MyList.push_back(10);
    MyList.push_back(20);
    MyList.push_back(30);
    MyList.push_back(40);
    MyList.push_back(50);

    //Display the content of the list.
    MyList.PrintList();  

    //delete odd nodes of the list
    MyList.deleteOddNodes();

    Console.WriteLine("After deleting odd nodes:");
    //Display the content of the list.
    MyList.PrintList();  
  }
}

The above code will give the following output: 

The list contains: 10 20 30 40 50 
After deleting odd nodes:
The list contains: 20 40 

<?php
//node structure
class Node {
  public $data;
  public $next;
}

class LinkedList {
  public $head;

  public function __construct(){
    $this->head = null;
  }
  
  //Add new element at the end of the list
  public function push_back($newElement) {
    $newNode = new Node();
    $newNode->data = $newElement;
    $newNode->next = null; 
    if($this->head == null) {
      $this->head = $newNode;
      $newNode->next = $this->head;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next !== $this->head) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
      $newNode->next = $this->head;
    }    
  }

  //delete odd nodes of the list
  public function deleteOddNodes() { 
    if($this->head != null && $this->head->next == $this->head) {
      $this->head = null;
    } else if($this->head != null) {
    
      $temp = $this->head;
      while($temp->next != $this->head) {
        $temp = $temp->next;
      }
      $temp->next = $this->head->next;
      $this->head = null;
      $this->head = $temp->next;

      if($this->head != null && $this->head->next != $this->head) {

        $evenNode = $this->head;
        $oddNode = $this->head->next; 
        while(true) {
          $temp = $evenNode;
          $evenNode->next = $oddNode->next;
          $oddNode = null;
          $evenNode = $evenNode->next;
          $oddNode = $evenNode->next;
          if($evenNode == $this->head || $oddNode == $this->head)
            break;
        }

        if($evenNode == $this->head)
          $temp->next = $this->head;
        else
          $evenNode->next = $this->head;
      }
    } 
  } 

  //display the content of the list
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while(true) {
        echo $temp->data." ";
        $temp = $temp->next;
        if($temp == $this->head)
          break;        
      }
      echo "\n";
    } else {
      echo "The list is empty.\n";
    }
  }    
};

// test the code  
$MyList = new LinkedList();

//Add five elements in the list.
$MyList->push_back(10);
$MyList->push_back(20);
$MyList->push_back(30);
$MyList->push_back(40);
$MyList->push_back(50);

//Display the content of the list.
$MyList->PrintList();

//delete odd nodes of the list
$MyList->deleteOddNodes();

echo "After deleting odd nodes:\n";
//Display the content of the list.
$MyList->PrintList();
?>

The above code will give the following output: 

The list contains: 10 20 30 40 50 
After deleting odd nodes:
The list contains: 20 40
AlphaCodingSkills
AlphaCodingSkills Android App
Facebook Page Twitter Page LinkedIn Page
Learning Tutorials
Learning Tutorials
Useful Links
Python Libraries
About Us  |  Privacy Policy  |  Contact Us
AlphaCodingSkills is a online learning portal that provides tutorials on Python, Java, C++, C, C#, PHP, R, Ruby, Rust, Scala, Swift, Perl, SQL, Data Structures and Algorithms. Tutorials, examples, references and content of the website are reviewed and simplified continuously to improve comprehensibility and eliminate any possible error. We use cookies to ensure best browsing experience on our website. While using this website, you acknowledge to have read and accepted our cookie and privacy policy.