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