链接列表可以用以下结构表示：-
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; }你被赋予了一个功能，
struct Node* ReArrangeVowelsAndConsonants(struct Node* head);struct Node* ReArrangeVowelsAndConsonants(struct Node* head);static Node ReArrangeVowelsAndConsonants(Node head);static Node ReArrangeVowelsAndConsonants(Node head);指针"head"指向链接列表的开头。实现重新排列和返回相同列表的功能，使所有元音占据列表的前半部分，所有辅音占据列表的后半部分。
注：
- 不要创建新列表，请修改现有列表
- 元音和辅音的相对顺序不应在它们之间发生变化
- 你可以假设这个列表的长度是偶数，一半的节点包含元音，另一半包含辅音
- 如果列表为NULL，则返回NULL
示例：
输入：
a->k->r->i->t->e->o->m输出：
a->i->e->o->k->r->t->m说明：
列表前半部分中的辅音k和r被移到列表后半部分，而列表后半部分中的元音e和o被移到表前半部分，保持相对顺序不变。
我的代码正确执行操作，但不满足注释中的第2点。元素的相对顺序在我的输出中发生了变化，因为我正在与元音交换子成分。我的代码如下。。。。我只需要如何使我的代码也适用于这种情况。
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;
do
{
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 the number of characters:");
int length=s.nextInt();
System.out.println("Enter the character seperated by ->");
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]);
}
}
我认为这个练习使用链表而不是数组是有原因的。如果允许返回一个新头，则可以使用重新排列节点本身的方法，而不是在现有节点之间交换数据。这种方法的优点是只需要遍历列表一次。
这个实现的想法是保留我们发现的最新元音的标记。如果我们找到另一个元音，我们将其从链中取出，并将其放在现有的最新元音之后。例如：
a->b->c->i->x->e
假设我们的latestVowel引用引用了a节点，并且我们当前已到达i节点。我们做：
a->i->b->c->x->e
因此，在a之后的内容现在在i之后，而a直接链接到i。
要正确删除和添加链接，最好在检查之前使用项。所以，如果你有一个curr，你会检查curr.next，看看它是否是元音。如果是，那么通过将其next分配给curr的下一个，可以很容易地将其从链中删除。当然，在你这样做之前，你需要把它添加到新的位置，否则你可能会有一条悬空的链条。
以下是方法，并附有注释来解释每个部分：
public static Node rearrangeVowelsAndConsonants(Node head) {
Node newHead = head;
Node latestVowel;
Node curr = head;
if (head == null) {
return null;
}
// We need to discover the first vowel in the list. It is going to be
// the returned head, and also the initial latestVowel.
if (isVowel(head.data)) {
// Easy: first element is a vowel. It will also be the new head
// and the initial latestVowel;
latestVowel = head;
} else {
// First element is not a vowel. Iterate through the list until we
// find a vowel. Note that curr points to the element *before*
// the element with the vowel.
while (curr.next != null && !isVowel(curr.next.data)) {
curr = curr.next;
}
// This is an edge case where there are only consonants.
if (curr.next == null) {
return head;
}
// Set the initial latestVowel and the new head to the vowel
// item that we found. Relink the chain of consonants after
// that 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;
}
// Now traverse the list. Curr is always the item *before* the one we are
// checking, so that we can use it to re-link.
while ( curr != null && curr.next != null ) {
if (isVowel(curr.next.data)) {
// The next discovered item is a vowel
if (curr == latestVowel) {
// If it comes directly after the previous vowel, we don't need
// to move items around, just mark the new latestVowel and
// advance curr.
latestVowel = curr = curr.next;
} else {
// But if it comes after an intervening chain of consonants,
// we need to chain the newly discovered vowel right after
// the old vowel. Curr is not changed as after the re-linking
// it will have a new next, that has not been checked yet,
// and we always keep curr at one before the next to 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 from previous place
latestVowel.next = temp; // Re-link the chain of consonants after lastestVowel.
}
} else {
// No vowel in the next element, advance curr.
curr = curr.next;
}
}
return newHead;
}
您可以实现另一种排序算法。如果你不通过用辅音替换元音进行排序，而是通过将元音与前一个元素(如果是辅音(逐一替换来进行排序，你会对列表进行排序，元音和辅音之间的相对顺序不会受到影响。
如果你不确定如何实现这样的排序算法，请查看冒泡排序：
气泡排序Wikipedia
// Here is the Correct Answer after merging the previous answers.
// It works Correctly...!
// Splitting Vowels And Consonants
import java.util.Scanner;
import java.util.StringTokenizer;
public class Node
{
public char data;
public Node next;
public static Node rearrangeVowelsAndConsonants(Node head) {
Node newHead = head;
Node latestVowel;
Node curr = head;
if (head == null) {
return null;
}
if (isVowel(head.data)) {
latestVowel = head;
} else {
while (curr.next != null && !isVowel(curr.next.data)) {
curr = curr.next;
}
if (curr.next == null) {
return head;
}
latestVowel = newHead = curr.next;
curr.next = curr.next.next;
latestVowel.next = head;
}
while ( curr != null && curr.next != null ) {
if (isVowel(curr.next.data)) {
if (curr == latestVowel) {
latestVowel = curr = curr.next;
} else {
Node temp = latestVowel.next;
latestVowel.next = curr.next;
latestVowel = latestVowel.next;
curr.next = curr.next.next;
latestVowel.next = temp;
}
} else {
curr = curr.next;
}
}
return newHead;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner s=new Scanner(System.in);
int count=0;
System.out.println("Enter the character seperated by ->");
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=rearrangeVowelsAndConsonants(a[0]);
while(start.next!=null)
{
System.out.print(start.data+"->");
start=start.next;
}
System.out.println(start.data);
s.close();
}
public static boolean isVowel(char ch)
{
if(ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')
{
return true;
}
else
return false;
}
}