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

Linked List - Delete odd nodes

Deleting odd nodes of a linked list requires traverse through the list and deleting odd nodes one by one. If the list is not null then release the head and make next of head as new head. If the new head is not null then create two nodes - evenNode and oddNode. Make evenNode to the first even node of list and oddNode to second odd node of the list (3rd node in the original list). If both are not null, delete the oddNode and adjust links. Move both nodes to next set of even-odd nodes. Repeat the process till the any or both nodes become null.

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

void deleteOddNodes() {
  if(head != NULL) {
    
    //1. if head is not null, make next of head as
    //   new head and delete previous head
    Node* temp = head;
    head = head->next; 
    free(temp);   
    if(head != NULL) {

      //2. if the new head is not null create 
      //   nodes - evenNode and oddNode
      Node* evenNode = head;
      Node* oddNode = head->next; 

      while(evenNode != NULL && oddNode != NULL) {
        
        //3. while evenNode and oddNode are not null
        //   make next of evenNode as next of oddNode 
        //   and free oddNode   
        evenNode->next = oddNode->next;
        free(oddNode);

        //4. and make evenNode as next of evenNode
        evenNode = evenNode->next;
        
        //5. Update evenNode and oddNode
        if(evenNode != NULL)
          oddNode = evenNode->next;
      }
    }
  }
} 

void deleteOddNodes(struct Node** head_ref) {
  if(*head_ref != NULL) {
    
    //1. if head is not null, make next of head as
    //   new head and delete previous head
    struct Node* temp = *head_ref;
    *head_ref = (*head_ref)->next;
    free(temp);
    if(*head_ref != NULL) {
      
      //2. if the new head is not null create 
      //   nodes - evenNode and oddNode
      struct Node* evenNode = *head_ref;
      struct Node* oddNode = (*head_ref)->next;

      while(evenNode != NULL && oddNode != NULL) {
        
        //3. while evenNode and oddNode are not null
        //   make next of evenNode as next of oddNode 
        //   and free oddNode   
        evenNode->next = oddNode->next;
        free(oddNode);

        //4. and make evenNode as next of evenNode
        evenNode = evenNode->next;
        
        //5. Update evenNode and oddNode
        if(evenNode != NULL)
          oddNode = evenNode->next;
      }
    }
  }   
}     

def deleteOddNodes(self):  
  if (self.head != None):
    
    #1. if head is not null, make next of head as
    #   new head and delete previous head
    temp = self.head
    self.head = self.head.next
    temp = None
    if (self.head != None):
      
      #2. if the new head is not null create 
      #   nodes - evenNode and oddNode
      evenNode = self.head
      oddNode = self.head.next 

      while(evenNode != None and oddNode != None):
        
        #3. while evenNode and oddNode are not null
        #   make next of evenNode as next of oddNode
        #   and free oddNode   
        evenNode.next = oddNode.next
        oddNode = None

        #4. and make evenNode as next of evenNode
        evenNode = evenNode.next
        
        #5. Update evenNode and oddNode
        if(evenNode != None):
          oddNode = evenNode.next

void deleteOddNodes() {
  if(this.head != null) {
    
    //1. if head is not null, make next of head as
    //   new head and delete previous head
    Node temp = this.head;
    this.head = this.head.next;
    temp = null;
    if(this.head != null) {
      
      //2. if the new head is not null create 
      //   nodes - evenNode and oddNode
      Node evenNode = this.head;
      Node oddNode = this.head.next; 

      while(evenNode != null && oddNode != null) {
        
        //3. while evenNode and oddNode are not null
        //   make next of evenNode as next of oddNode 
        //   and free oddNode  
        evenNode.next = oddNode.next;
        oddNode = null;

        //4. and make evenNode as next of evenNode
        evenNode = evenNode.next;
        
        //5. Update evenNode and oddNode
        if(evenNode != null)
          oddNode = evenNode.next;
      }
    }
  }
}         

public void deleteOddNodes() {
  if(this.head != null) {
    
    //1. if head is not null, make next of head as
    //   new head and delete previous head
    Node temp = this.head;
    this.head = this.head.next;
    temp = null;
    if(this.head != null) {  
      
      //2. if the new head is not null create 
      //   nodes - evenNode and oddNode
      Node evenNode = this.head;
      Node oddNode = this.head.next; 

      while(evenNode != null && oddNode != null) {
        
        //3. while evenNode and oddNode are not null
        //   make next of evenNode as next of oddNode 
        //   and free oddNode  
        evenNode.next = oddNode.next;
        oddNode = null;

        //4. and make evenNode as next of evenNode
        evenNode = evenNode.next;
        
        //5. Update evenNode and oddNode
        if(evenNode != null)
          oddNode = evenNode.next;
      }
    }
  }
}        

public function deleteOddNodes() {
  if($this->head != null) {
    
    //1. if head is not null, make next of head as
    //   new head and delete previous head
    $temp = $this->head;
    $this->head = $this->head->next;
    $temp = null;
    if($this->head != null) { 
      
      //2. if the new head is not null create 
      //   nodes - evenNode and oddNode
      $evenNode = $this->head;
      $oddNode = $this->head->next; 

      while($evenNode != null && $oddNode != null) {
        
        //3. while evenNode and oddNode are not null
        //   make next of evenNode as next of oddNode 
        //   and free oddNode  
        $evenNode->next = $oddNode->next;
        $oddNode = null;

        //4. and make evenNode as next of evenNode
        $evenNode = $evenNode->next;
        
        //5. Update evenNode and oddNode
        if($evenNode != null)
          $oddNode = $evenNode->next;
      }
    }
  }
}

The below is a complete program that uses above discussed concept of deleting odd nodes of a 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;
      } else {
        Node* temp = head;
        while(temp->next != NULL)
          temp = temp->next;
        temp->next = newNode;
      }    
    }
    
    //delete odd nodes of the list
    void deleteOddNodes() {
      if(head != NULL) {
        Node* temp = head;
        head = head->next; 
        free(temp);   
        if(head != NULL) {
          Node* evenNode = head;
          Node* oddNode = head->next; 
          while(evenNode != NULL && oddNode != NULL) {  
            evenNode->next = oddNode->next;
            free(oddNode);
            evenNode = evenNode->next;
            if(evenNode != NULL)
              oddNode = evenNode->next;
          }
        }
      }
    } 

    //display the content of the list
    void PrintList() {
      Node* temp = head;
      if(temp != NULL) {
        cout<<"The list contains: ";
        while(temp != NULL) {
          cout<<temp->data<<" ";
          temp = temp->next;
        }
        cout<<"\n";
      } 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; 
  } else {
    temp = *head_ref;
    while(temp->next != NULL) {
      temp = temp->next;
    }    
    temp->next = newNode;
  }
}

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

//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 (temp != NULL) {
      printf("%i ",temp->data);
      temp = temp->next;  
    }
    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
      return
    else:
      temp = self.head
      while(temp.next != None):
        temp = temp.next
      temp.next = newNode

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

  #display the content of the list
  def PrintList(self):
    temp = self.head
    if(temp != None):
      print("The list contains:", end=" ")
      while (temp != None):
        print(temp.data, end=" ")
        temp = temp.next
      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;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != null)
        temp = temp.next;
      temp.next = newNode;
    }    
  }

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

  //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(temp != null) {
        System.out.print(temp.data + " ");
        temp = temp.next;
      }
      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;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != null)
        temp = temp.next;
      temp.next = newNode;
    }    
  }

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

  //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(temp != null) {
        Console.Write(temp.data + " ");
        temp = temp.next;
      }
      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;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next != null) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
    }    
  }

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

  //display the content of the list
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while($temp != null) {
        echo $temp->data." ";
        $temp = $temp->next;
      }
      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.