Facebook Page Twitter Page LinkedIn Page
× C# Data Structures - Linked List Other Related Topics


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.

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;
      }
    }
  }
}        

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

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("\nThe list contains: ");
      while(temp != null) {
        Console.Write(temp.data + " ");
        temp = temp.next;
      }
    } else {
      Console.Write("\nThe 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.Write("\nAfter 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