Segregate even and odd nodes in a linked list java. Use the following function to segregate the even and odd nodes in a given linked list.
/*
* Time Complexity O(n)
*/
public Node segragateEventAndOdd(Node head) {
Node os, oe, es, ee;
os = oe = es = ee = null;
Node current = head;
while(current != null) {
if(current.data%2==0) {//Even
if(es == null) {//Even start is empty
es = current;
ee = current;
}else {
ee.next = current;
ee = ee.next;
}
}else {//Odd
if(os == null) {//Odd start empty
os = current;
oe = current;
}else {//Odd end not empty
oe.next = current;
oe = oe.next;
}
}
current = current.next;
}
//Check even start empty or odd start empty
if(es == null || oe == null) {
return null;
}
ee.next = os;
oe.next = null;
return es;
}
public void print(Node head) {
while(head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
Following code copy and paste into your test class:-
/* Segregate the event and odd nodes */
LinkedList segregateLinkedList = new LinkedList();
segregateLinkedList.insertEnd(17);
segregateLinkedList.insertEnd(15);
segregateLinkedList.insertEnd(8);
segregateLinkedList.insertEnd(12);
segregateLinkedList.insertEnd(10);
segregateLinkedList.insertEnd(5);
segregateLinkedList.insertEnd(7);
segregateLinkedList.insertEnd(11);
Node nodeHead = segregateLinkedList.insertEnd(4);
System.out.println("\nLinked List:- ");
segregateLinkedList.print(nodeHead);
Output:-
Linked List:-
17 15 8 12 10 5 7 11 4
After Segregated Linked List:-
8 12 10 4 17 15 5 7 11
