不使用 tail 实现功能

Question

我创建了一个程序来反转单词的非元音序列，由一个简单的链表表示，但我应该这样做而不使用指向最后一个节点的尾指针。

我在 createList、pop（用于弹出列表和每个节点的 return 字母字符）、push_back 和 push_front 中使用了此功能（两者都用于反转非元音序列。例如，push_front 将一个节点放在包含所分析序列的列表前面：node-> a-> b-> c。push_back，在同理，使得序列a->b->c为a->b->c->node).

LIST *createList(void){
    LIST *list = malloc(sizeof(*list));
    if(list){
        list->first = list->tail = NULL;
    }
    return list;
}

char pop(LIST *list){
    char ch = list->first->letter;

    list->first = list->first->next;
    if(list->first == NULL)
        list->tail = NULL;
    return ch;
}

void push_back(LIST *list, char ch){
    NODE *node = createNode(ch);
    if(list->first)
        list->tail = list->tail->next = node;
    else
        list->tail = list->first = node;
}

void push_front(LIST *list, char ch){
    NODE *node = createNode(ch);
    if(list->first){
        node->next = list->first;
        list->first = node;
    } else {
        list->tail = list->first = node;
    }
}

我想知道如何用某些局部变量或上述函数的其他实现替换 typedef 中的尾指针。

Answer 1

你真的只需要更改 push_back 因为它推到列表的末尾

void push_back(LIST *list, char ch){
    NODE *node = createNode(ch);
    NODE *tmp = list->first;

    if (tmp)
      while(tmp)
      {
         if (tmp->next == NULL)
         { 
            tmp->next = node;
            tmp = tmp->next;
         }
         tmp = tmp->next;         
      }
    else
      list->first = node;
}

您可以在此处找到完整的实现 https://repl.it/KiBB/6

不使用 tail 实现功能

Implement functions without using tail

c

linked-list

tail

data-structures