1

The following is the code I have written to solve the particular problem. But I am having problems with solving two edge cases. The case where the first element itself is a vowel, and the case where the last element is the vowel. Now as for the first edge case, I think it can be solved by iterating through the list till we find a vowel, and inserting the head node before the said node, and update the head pointer. But in the 2nd case, the case where the last element is a vowel, in that case, my code is running into an infinite loop. How can I handle that particular case? Also, if you can suggest any different approach towards solving the problem, please do so and if you can, please suggest any kind of improvement I can apply in the code.

#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);
}
4

1 回答 1

1

要处理最后一个元素是元音的第二种边缘情况：替换

while (temp!=fin)

和

while (temp->next!=fin)

事实是您不需要检查fin. 如果它是一个元音，那么它已经被隔离到最后。如果它的辅音也满足条件。无论哪种方式都不会影响结果。当然，当 size 为 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)

于 2013-07-15T18:40:46.400 回答