数据结构——在java中，将链表中所有现有的元音移到链表的末尾

Question

我实际上是在尝试实现一个链表，它在最后使用java移动列表中所有现有的元音。意思是，给定一个链表(链接)，在每个节点中包含字符，我需要以这样一种方式隔离它的节点，即所有具有元音的节点通过保持其原始顺序移动到链表的末尾。

输出应该像:

original list: w->e->r->s->o->m->a->t
Output needed: w->r->s->m->t->a->e->o

我想在java中实现这个。请让我知道做它的优化方式是什么(比如不使用任何额外的列表)。如有任何建议或帮助，我将不胜感激。

Answer 1

Try

    LinkedList<Character> list = new LinkedList<>(Arrays.asList('w', 'e', 'r', 's', 'o', 'm', 'a', 't'));
    int n = list.size();
    for(int i = 0; i < n; i++) {
        char c = list.get(i);
        if ("aeiuoAEIUO".indexOf(c) != -1) {
            list.remove(i);
            list.add(c);
            n--;
        }
    }
    System.out.println(list);

输出

[w, r, s, m, t, e, o, a]

Answer 2

您可以这样做，但很可能有一种更有效的方法。

private LinkedList reOrder(LinkedList<Character> chars) {
    LinkedList<Character> temporary = new LinkedList<Character>();
    for(Character a: chars) {
        if(a=='a' || a=='e' || a=='i' ||
           a=='y' || a=='u' || a=='o') {
            temporary.add(a);
        }
    }
    chars.removeAll(temporary);
    chars.addAll(temporary);
    return chars;
}

Answer 3

我将定义一个自定义Comparator对象，然后使用Collections.sort对列表进行排序。这里我定义了一个比较器，当用作sort的参数时，它将把所有元音移到末尾:

class VowelSort implements Comparator<Character>
{
    private static boolean isVowel(Character c)
    {
        return "AEIOUaeiou".contains(c.toString());
    }
    public int compare(Character arg0, Character arg1)
    {
        final boolean vowel0 = isVowel(arg0), vowel1 = isVowel(arg1);
            //if neither of the characters are vowels, they are "equal" to the sorting algorithm
        if (!vowel0 && !vowel1) 
            {
            return 0;
        }
            //if they are both vowels, compare lexigraphically
        if (vowel0 && vowel1)
            {
            return arg0.compareTo(arg1);
        }
            //vowels are always "greater than" consonants
        if (vowel0 && !vowel1)
            {
            return 1;
        }
            //and obviously consonants are always "less than" vowels
        if (!vowel0 && vowel1)
            {
            return -1;
        }
        return 0; //this should never happen
    }
}

主要…

Collections.sort(chars,new VowelSort());

如果您希望对辅音进行排序，只需更改

//if neither of the characters are vowels, they are "equal" to the sorting algorithm
if (!vowel0 && !vowel1)
{
        return 0;
}

//compare consonants lexigraphically
if (!vowel0 && !vowel1)
{
        return arg0.compareTo(arg1);
}

Answer 4

这确实是语言不可知论，但这里有一个方法:

在列表中迭代一次，创建一个新列表，并从原始列表中删除遇到的每个元音，并将它们放入新列表中。

最后，只需将新列表附加到原始列表上。当你删除元音时，你会把所有的元音都移到列表的末尾。

Answer 5

创建您自己的抽象数据结构，您可以将内容存储为字符数组。

char[] word = new char[] { 'f', 'o', 'o', 'b', 'a', 'r' };
char[] reordered = new char[word.length];
int vowel = word.length - 1;
int nonVowel = 0;
for (int i = 0; i < word.length; i++) {
    switch (word[i]) {
    case 'a':
    case 'e':
    case 'i':
    case 'o':
    case 'u':
        reordered[vowel] = word[i];
        vowel--;
        break;
    default:
        reordered[nonVowel] = word[i];
        nonVowel++;
        break;
    }
}

现在，非元音的顺序是正确的，但是元音的顺序是相反的。根据您的用例，您可以反转元音子顺序或定义"get(position)"，其中您返回:

if (position < nonVowel)
            return reordered[position];
        else
            return reordered[reordered.length - (position - vowel)];