Seperatiing vowels and consonents of Linked List in Java -

a linked list can represented following structure:-

struct node { char data; struct node* next; }; struct node { char data; struct node* next; };class node { public char data; public node next; }class node { public char data; public node next; } 

you given function,

struct node* rearrangevowelsandconsonants(struct node* head);struct node*   rearrangevowelsandconsonants(struct node* head);static node   rearrangevowelsandconsonants(node head);static node   rearrangevowelsandconsonants(node head); 

the pointer 'head' points start of linked list. implement function rearrange , return same list vowels occupy first half of list , consonants occupy second half.

note:

1. do not create new list, modify existing list.
2. relative ordering of vowels , consonants should not change among themselves.
3. you may assume list of length , half nodes contain vowels , other half contain consonants.
4. if list null, return null.

example:

input:
-> k -> r -> -> t -> e -> o -> m

output:
- >i - > e -> o -> k -> r -> t -> m

explanation:
consonants k , r in first half of list moved second half of list, while vowels e , o in second half of list moved first half of list, keeping relative ordering same.

my code performs operation correctly not satisfy point 2 in note. relative ordering of elements changes in output swapping consonents vowels. code below....i need how make code work case also.

import java.io.*; import java.lang.*; import java.util.*; public class node {     public char data;     public node next;     public static node rearrange(node head)     {         node start=new node();         node curr=new node();         node temp=new node();         start=curr=head;         int begin=0;         int flag=0;         while(head.next!=null)         {              if(head.data=='a'||head.data=='e'||head.data=='i'||head.data=='o'||head.data=='u')             {      // no change             }             else             {                 curr=head.next;                                 {                      system.out.println("curr "+curr.data+" head "+head.data);                     if(curr.data=='a'||curr.data=='e'||curr.data=='i'||curr.data=='o'||curr.data=='u')                     {                      temp.data=curr.data;                      curr.data=head.data;                      head.data=temp.data;                      break;                     }                 }while((curr=curr.next)!=null);             }             head=head.next;         }          while(start.next!=null)         {             system.out.print(start.data+"->");             start=start.next;         }         system.out.print(start.data);         return start;      }     public static void main(string args[])     {       scanner s=new scanner(system.in);       int count=0;       system.out.println("enter number of characters:");       int length=s.nextint();       system.out.println("enter character seperated ->");       string inp=s.next();       stringtokenizer st=new stringtokenizer(inp,"->");       node[] a=new node[inp.length()];       for(int i=0;st.hasmoreelements();i++)       {         a[i]=new node();         a[i].data=(st.nexttoken().tostring()).charat(0);         count++;       }       a[count-1].next=null;       for(int i=0;i<(count-1);i++)       {         a[i].next=a[i+1];       }       node start =new node();       start=rearrange(a[0]);     } } 

i think there reason why exercise using linked lists rather array. if allowed return new head, rather exchanging data between existing nodes, can use method rearranges nodes themselves. advantage of method need traverse list once.

the idea of implementation keep marker of latest vowel found. if find vowel, take out of chain , put after existing latest vowel. e.g.:

 -> b -> c -> -> x -> e 

say our latestvowel reference references a node, , reached i node. do:

 -> -> b -> c -> x -> e 

so after a after i, , a links directly i.

to remove , add links, it's best use item before 1 checking. if have curr, check curr.next see if it's vowel or not. if is, it's easy remove chain assigning next curr's next. of course need add new place before that, or might have dangling chain.

here method, comments explain each part:

public static node rearrangevowelsandconsonants(node head) {     node newhead = head;     node latestvowel;     node curr = head;      if (head == null) {         return null;     }      // need discover first vowel in list. going     // returned head, , initial latestvowel.     if (isvowel(head.data)) {         // easy: first element vowel. new head         // , initial latestvowel;         latestvowel = head;     } else {         // first element not vowel. iterate through list until         // find vowel. note curr points element *before*         // element vowel.         while (curr.next != null && !isvowel(curr.next.data)) {             curr = curr.next;         }         // edge case there consonants.         if (curr.next == null) {             return head;         }         // set initial latestvowel , new head vowel         // item found. relink chain of consonants after         // vowel item:         // old_head_consonant->consonant1->consonant2->vowel->rest_of_list becomes         // vowel->old_head_consonant->consonant1->consonant2->rest_of_list         latestvowel = newhead = curr.next;         curr.next = curr.next.next;         latestvowel.next = head;     }      // traverse list. curr item *before* 1     // checking, can use re-link.     while ( curr != null && curr.next != null ) {         if (isvowel(curr.next.data)) {             // next discovered item vowel             if (curr == latestvowel) {                 // if comes directly after previous vowel, don't need                 // move items around, mark new latestvowel ,                 // advance curr.                 latestvowel = curr = curr.next;             } else {                 // if comes after intervening chain of consonants,                 // need chain newly discovered vowel right after                 // old vowel. curr not changed after re-linking                 // have new next, has not been checked yet,                 // , keep curr @ 1 before next check.                 node temp = latestvowel.next;   // keep start of consonant chain                 latestvowel.next = curr.next;   // chain in new vowel                 latestvowel = latestvowel.next; // advance latestvowel                 curr.next = curr.next.next;     // remove found vowel previous place                 latestvowel.next = temp;        // re-link chain of consonants after lastestvowel.             }         } else {             // no vowel in next element, advance curr.             curr = curr.next;         }     }     return newhead; }