将链接列表中的元音移至开头

Question

我正在解决一个给定链接的字符列表的问题，我们必须将元音移动到开头，以便元音和辅音按时间顺序排列。这是按照它们出现在原始列表中的顺序。

Input : S->T->A->C->K->O->V->E->R->F->L->O->W

Output : A->O->E->O->S->T->C->K->V->R->F->L->W

我做到了通过列表遍历一次，并创建了两个列表称为元音和辅音，后来它们合并。

可以在不创建额外列表的情况下完成吗？我的意思是可能使用指针操作？

Answer 1

记住列表的开始。当你遇到元音时，将它移到列表的开头;元音成为你记忆中的新开始。

Answer 2

1. Traverse the list 
2. When you encounter a vowel, check with head if its smaller or greater 
3. If smaller, re-place new vowel before head, else move head and check again 
4. In the end relocate head to first 

    temp = head; 
    while(current.next != null) { 
     if(current.isVowel()) { 
     if(head.isVowel()) { 
      //check the precedence 
      //Re-place the current with temp 
     } 
     else { 
      //Re-place current in front of head 
     } 
     } 
     current = current.next; 
    } 

这是一个抽象的理解。正确实施。

Answer 3

#include <stdio.h> 
#include <string.h> 
#include <ctype.h> 

struct list { 
    struct list *next; 
    int ch; 
    }; 
#define IS_VOWEL(p) strchr("aeiouy", tolower(p->ch)) 
struct list *shuffle ( struct list *lst) 
{ 
    struct list *new=NULL, **dst, **src; 
    dst = &new; 
    for (src = &lst; *src;) { 
      struct list *this; 
      this= *src; 
      if (!IS_VOWEL(this)) { src= &(*src)->next; continue; } 
      *src = this->next; 
      this->next = *dst; 
      *dst = this; 
      dst = & (*dst)->next; 
      } 
    *dst = lst; 
    return new; 
} 

int main (void) 
{ 
    struct list arr[] = { {arr+1, 'S'} , {arr+2, 'T'} , {arr+3, 'A'} 
     , {arr+4, 'C'} , {arr+5, 'K'} , {arr+6, 'O'} 
     , {arr+7, 'V'} , {arr+8, 'E'} , {arr+9, 'R'} 
     , {arr+10, 'F'} , {arr+11, 'L'} , {arr+12, 'O'} , {NULL, 'W'} }; 
    struct list *result; 

    result = shuffle (arr); 

    for (; result; result = result->next) { 
     printf("-> %c" , result->ch); 
     } 
    printf("\n"); 

return 0; 
} 

OUTPUT：

- > A-> O-> E-> O-> S-> T-> C-> K-> V-> R-> F-> L- > W

Answer 4

你可以非常容易地修改指针来创建两个独立的列表，而不必重复任何节点，这就是我假设你说的意思，当你说你想避免创建新的列表。只有原始节点中的指针才会被修改。

首先，让我们创建的数据结构的列表：

#include <stdio.h> 
#include <stdlib.h> 

// Structure for singly linked list. 

typedef struct sNode { 
    char ch; 
    struct sNode *next; 
} tNode; 

而接下来，我们提供两个实用的功能，第一个字符添加到列表：

// Append to list, not very efficient but debug code anyway. 

static tNode *append (tNode *head, char ch) { 
    // Allocate new node and populate it. 

    tNode *next = malloc (sizeof (tNode)); 
    if (next == NULL) { 
     puts ("Out of memory"); 
     exit (1); 
    } 
    next->ch = ch; 
    next->next = NULL; 

    // First in list, just return it. 

    if (head == NULL) 
     return next; 

    // Else get last, adjust pointer and return head. 

    tNode *this = head; 
    while (this->next != NULL) 
     this = this->next; 
    this->next = next; 
    return head; 
} 

而第二个转储用于调试目的的列表：

// Debug code to dump a list. 

static void dump (tNode *this) { 
    if (this == NULL) 
     return; 
    printf ("(%08x)%c", this, this->ch); 
    while ((this = this->next) != NULL) 
     printf (" -> (%08x)%c", this, this->ch); 
    putchar ('\n'); 
} 

除此之外，我们需要一个简单的方法来告诉if一个节点是一个元音还是不是。对于我们而言，我们将只使用大写字母：

// Check for vowel (uppercase only here). 

static int isVowel (tNode *this) { 
    char ch = this->ch; 
    return (ch == 'A') || (ch == 'E') || (ch == 'I') 
     || (ch == 'O') || (ch == 'U'); 
} 

现在，这是最重要的一点，它可以将一个列表分成两个不同的列表（一个元音，辅音一个）位。哪个列表是哪种类型取决于列表中的第一个条目。

基本上做的是从列表开头的所有公共节点（本例中为“ST”），下一个不匹配类型的另一个子列表（“A “），然后开始逐个处理剩余的节点，从”C“开始。

随着每个后续节点的检查，指针将被调整为将其添加到第一个或第二个列表（同样，实际上不会创建新的节点，实际上将创建）。一旦我们到达列表末尾的NULL，我们就决定是否将第二个列表追加到第一个列表中，反之亦然（元音必须先出现）。

这一切的指针操作的代码如下所示：

// Meat of the solution, reorganise the list. 

static tNode *regroup (tNode *this) { 
    // No reorg on empty list. 

    if (this == NULL) 
     return this; 

    // Find first/last of type 1 (matches head), first of type 2. 

    tNode *firstTyp1 = this, *firstTyp2 = this, *lastTyp1 = this, *lastTyp2; 
    while ((firstTyp2 != NULL) && (isVowel (firstTyp1) == isVowel (firstTyp2))) { 
     lastTyp1 = firstTyp2; 
     firstTyp2 = firstTyp2->next; 
    } 

    // No type 2 means only one type, return list as is. 

    if (firstTyp2 == NULL) 
     return firstTyp1; 

    // Type 2 list has one entry, next node after that is for checking. 

    lastTyp2 = firstTyp2; 
    this = firstTyp2->next; 

    //dump (firstTyp1); 
    //dump (firstTyp2); 
    //putchar ('\n'); 

    // Process nodes until list is exhausted. 

    while (this != NULL) { 
     // Adjust pointers to add to correct list. 

     if (isVowel (this) == isVowel (lastTyp1)) { 
      lastTyp2->next = this->next; 
      lastTyp1->next = this; 
      lastTyp1 = this; 
     } else { 
      lastTyp1->next = this->next; 
      lastTyp2->next = this; 
      lastTyp2 = this; 
     } 

     // Advance to next node. 

     this = this->next; 

     //dump (firstTyp1); 
     //dump (firstTyp2); 
     //putchar ('\n'); 
    } 

    // Attach last of one list to first of the other, 
    // depending on which is the vowel list. 

    if (isVowel (firstTyp1)) { 
     lastTyp1->next = firstTyp2; 
     return firstTyp1; 
    } 

    lastTyp2->next = firstTyp1; 
    return firstTyp2; 
} 

最后，没有复杂的程序将是不完整的一些描述一个测试工具，所以这里是一些创建和转储在其最初形式的列表，然后重新组织并转储结果：

int main (void) { 
    char *str = "STACKOVERFLOW"; 
    tNode *list = NULL; 

    while (*str != '\0') 
     list = append (list, *(str++)); 

    dump (list); 
    puts(""); 

    list = regroup (list); 
    dump (list); 

    return 0; 
} 

一旦进入，编译并运行所有的代码，结果不出所料：

(09c03008)S -> (09c03018)T -> (09c03028)A -> (09c03038)C -> 
(09c03048)K -> (09c03058)O -> (09c03068)V -> (09c03078)E -> 
(09c03088)R -> (09c03098)F -> (09c030a8)L -> (09c030b8)O -> 
(09c030c8)W 

(09c03028)A -> (09c03058)O -> (09c03078)E -> (09c030b8)O -> 
(09c03008)S -> (09c03018)T -> (09c03038)C -> (09c03048)K -> 
(09c03068)V -> (09c03088)R -> (09c03098)F -> (09c030a8)L -> 
(09c030c8)W 

如果这是很难读，我会摆脱指针，只是列出字顺序：

S -> T -> A -> C -> K -> O -> V -> E -> R -> F -> L -> O -> W 
A -> O -> E -> O -> S -> T -> C -> K -> V -> R -> F -> L -> W