Linked List: Delete Alternating Nodes

Question: Given a linked list, delete alternating nodes. For example is the linked list is 4->6->10->8->9->10->18->20, then the output should be 4->10->9->18.

package additional_problems.linkedList;

/**
 * Created by aarushi on 28/6/21.
 */
public class P04DeleteAlternateNodes {
    public static void main(String[] args){
        // Create Linked List
        LinkedList list= new LinkedList();
        ListNode node= new ListNode(4);
        list.add(node);
        node= new ListNode(6);
        list.add(node);
        node= new ListNode(10);
        list.add(node);
        node= new ListNode(8);
        list.add(node);
        node= new ListNode(9);
        list.add(node);
        node= new ListNode(10);
        list.add(node);
        node= new ListNode(18);
        list.add(node);
        node= new ListNode(20);
        list.add(node);

              //print list
        list.printNoException();
        //delete the alternating nodes
        deleteAlternate(list);
        //print list
        list.printNoException();
    }

    //method to delete alternating nodes
    public static void deleteAlternate(LinkedList list) {
        //current: pointer which will point at the nodes whose next node has to be deleted
        ListNode current = list.head;

        //traverse till the last node
        while (current != null) {
            //delete the next node
            if (current.getNext() != null) {
                deleteNode(list, current.getNext());
            }
            //with the node deleted, assign move the current pointer to the next node
            current = current.getNext();
        }
    }

    public static void deleteNode(LinkedList list, ListNode node){
        try{
            list.delete(node);
        } catch (Exception e){
            System.out.println(e.getMessage());
        }
    }
}
package additional_problems.linkedList;

/**
 * Created by aarushi on 24/6/21.
 */
public class LinkedList {
    //data fields
    //head node
    ListNode head;

    //constructor to initialize head node
    public LinkedList() {
        head = null;
    }

    //function to add node to the end of the linked list
    public void add(ListNode node) {
        //if list is empty then set head equal to the node
        if (head == null) {
            head = node;
            node.setNext(null);
        } else {
            //create a pointer- temp
            ListNode temp = head;
            //iterate to the last element
            while (temp.getNext() != null) {
                temp = temp.getNext();
            }
            //insert the node at the end of the list
            temp.setNext(node);
            node.setNext(null);
        }
    }

    //method to delete the last node of the linked list
    public void delete(ListNode node) throws Exception {

        //throw exception if the list is empty
        if (head == null) {
            throw new Exception("List is empty");
        }

        //if the node passed is the head node then change the head pointer to the next node
        else if (node == head) {
            System.out.println(head.getData() + " deleted");
            head = head.getNext();
        } else {
            //pointer temp which will traverse the linked list
            ListNode temp = head;

            //find the node which points to the node to be deleted
            while (temp.getNext() != node && temp != null) {
                temp=temp.getNext();
            }

            //if node if found then delete the node otherwise throw an exception
            if (temp != null) {
                System.out.println(temp.getNext().getData() + " deleted");
                temp.setNext(node.getNext());
            } else {
                throw new Exception("Node not found");
            }

        }
    }

    public void printNoException() {
        if (head == null) {
            return;
        } else {
            ListNode temp = head;
            while (temp != null) {
                System.out.print(temp.getData() + " ");
                temp = temp.getNext();
            }
            System.out.println();
        }
    }

  

}
package additional_problems.linkedList;

/**
 * This class is the type declaration for a linked list
 * Created by aarushi on 24/6/21.
 */
public class ListNode {
    //data fields
    private int data; //stores the value of the node
    private ListNode next; //stores the reference of the next node

    //constructor to initialize the value of the node
    public ListNode(int data){
        this.data= data;
        this.subList=null;
    }

    //accessor method to get the value stored in data
    public int getData() {
        return this.data;
    }

    //mutator method to change the value of data
    public void setData(int data) {
        this.data = data;
    }

    //accessor method which returns the reference of the next node
    public ListNode getNext() {
        return this.next;
    }

    //mutator method which changes the reference of the next node
    public void setNext(ListNode next) {
        this.next = next;
    }

}

Leave a Reply

PHP JS HTML CSS BASH PYTHON CODE

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this:
search previous next tag category expand menu location phone mail time cart zoom edit close