在单链接列表末尾移动元音

Question

以下是

我为解决特定问题而编写的代码。但是我在解决两个边缘情况时遇到了问题。第一个元素本身是元音的情况，最后一个元素是元音的情况。现在至于第一个边缘情况，我认为可以通过遍历列表直到找到元音来解决，并在所述节点之前插入头节点，并更新头指针。但是在第两种情况下，最后一个元素是元音的情况下，在这种情况下，我的代码会进入无限循环。我该如何处理这种特殊情况？另外，如果您可以提出解决问题的任何不同方法，请这样做，如果可以，请提出我可以在代码中应用的任何改进。

#include<iostream>
using namespace std;
struct node
{
    char ch;
    node *next;
};
void enqueue (node **head, node **tail, char val)
{
    node *newn = (node *)malloc(sizeof(node));
    newn->ch = val;
    newn->next = NULL;
    if (*head == NULL)
    {
        *head = newn;
        *tail = newn;
    }
    (*tail)->next = newn;
    (*tail) = newn;
}
void print (node *head)
{
    while (head!=NULL)
    {
        cout<<head->ch<<" ";
        head = head->next;
    }
    cout<<endl;
}
bool isVowel (char ch)
{
    ch = ch | 32;
    if (ch == 'a' || ch =='e' || ch=='i' || ch=='o' || ch=='u')
        return true;
    return false;
}

node* segregateVowels (node *head, node *tail)
{
    if (head == NULL)
        return head;
    node *temp = head;
    node *fin = tail;
    while (temp!=fin)
    {
        cout<<temp->ch<<" "<<fin->ch<<endl;
        getchar();
        if (isVowel(temp->next->ch))
        {
            node *shift = temp->next;
            temp->next = temp->next->next;
            tail->next = shift;
            shift->next = NULL;
            tail = shift;
        }
        else
            temp = temp->next;
    }
    return head;
}

int main()
{
    srand(time(NULL));
    node *head = NULL, *tail = NULL;
    int i = 20;
    while (i>=0)
    {
        enqueue (&head, &tail, rand()%26+65);
        i--;
    }
    print(head);

    head = segregateVowels (head, tail);

    print(head);
}

Answer 1

要处理最后一个元素是元音的第二个边缘情况：取代

while (temp!=fin)

跟

while (temp->next!=fin)

事实是您无需检查fin的数据。如果它是一个元音，那么它已经隔离到最后了。如果它的辅音也满足条件。无论哪种方式，它都不会影响结果。当然，当大小为 1 时，您需要处理其他一些情况。

处理第一个边缘情况很简单。

编写一个小的 if 条件来检查头节点中的元音，并在while循环开始之前相应地更新指针。大功告成！

我有另一种简单的方法：假设它是双向链表...

取两个指针head(指向列表的开头(和tail(指向列表的末尾(。现在尝试理解以下代码：

int head_count=1, tail_count=linked_list_size;
while(head_count<tail_count)
{
     while(!isvowel(head->data) && head_count<=linked_list_size)
     {
         head=head->next;
         head_count++;
     }
     while(isvowel(tail->data) && tail_count>0)
     {
          tail=tail->prev;
          tail_count--;
      }
     if(tail_count>head_count)
     {//swap the values..
          char tmpc = head->data;
          head->data = tail->data;
          tail->data = head->data;
     } 
 }

时间复杂度：O(N)空间复杂度：O(1)

另一种使用额外O(N)空间的方法...

• 创建两个数组。. vowels和consonants阵列。
• 解析链表直到最后，并将所有字母存储到各自的数组中。
• 现在首先用数组中的字母覆盖链表中vowels然后用辅音数组覆盖链表中的数据。

时间复杂度：O(N)