如何反转队列的链表实现

Question

我正在尝试创建一个递归函数，它使用入队和出队函数来反转队列的链表实现。我试过这样做：

void reverse(queue *q, node *node)  //this first node would be passed like: reverse(&queue, queue->first);
{
        if(node->next == NULL)
        {
            return;
        }
        reverse(q, node->next);
        int tmp;
        q->head = node;
        tmp = dequeue(q);
        enqueue(q, tmp);
}
    
    void enqueue(queue *q, int data)
{
        node *node = (node*)malloc(sizeof(node));
        node->data = data;
        node->next = NULL;
    
        if (q->tail != NULL)
            q->tail->next = node;

        q->tail = node;

        if (q->head == NULL)
            q->head = node;
    
        q->tail = node;
}
    
    int dequeue(queue *q)
{
        if (!empty(q)){
            node *tmp = q->head;
            int result = tmp->data;
            q->head = tmp->next;
            if (q->head == NULL)
                q->tail = NULL;
            free(tmp);
            return result;
        }
 }

它在我的脑海中实际上是有意义的，但它只打印了前 2 个数字。

我们如何编写递归函数以使用入队和出队函数反转链接队列？

Answer 1

首先，你这一行有问题：

    node *node = (node*)malloc(sizeof(node));

当你用同名的指针遮蔽类型node时，给[=15的参数=] 是错误的。在该函数中使用不同的变量名。

此外，在 C 中，最好不要转换 what malloc returns:

    node *curnode = malloc(sizeof(node));
    // ...use curnode below ...

反向函数

这一行有问题：

q->head = node;

因为您刚刚反转了从 node->next 开始的队列，node->next 现在将成为队列的 tail，所以当您执行在上面的分配中，您将队列限制为两个元素，并丢失了对其他节点的引用。

作为解决方案，不要使用第二个函数参数，也不要使用 next 引用。只需出队 - 递归 - 并再次入队：

void reverse(queue *q)
{
    if (empty(q))
        return;
    int tmp = dequeue(q);
    reverse(q);
    enqueue(q, tmp);
}

Answer 2

对于初学者来说，您的方法效率低下，因为该函数会重新释放并分配所有节点。

它有一个错误。

考虑一个包含三个值为 1、2、3 的节点的队列。

在函数的第二次和第三次递归调用之后，您的队列类似于

3, 2

现在由于声明

q->head = node;

你有

1, 2

在这些电话之后

    tmp = dequeue(q);
    enqueue(q, tmp);

你有

2, 1

也就是值为3的节点丢失了

此外，该函数可以调用为空队列调用的未定义行为。

并且该函数应该只有一个参数：指向队列的指针。

无需对队列节点进行冗余动态重新分配，即可更简单地定义函数。例如

void reverse( queue *q )
{
    if (q->head != NULL && q->head->next != NULL)
    {
        node *current = q->head;
        q->head = q->head->next;
        reverse( q );
        q->tail->next = current;
        current->next = NULL;
        q->tail = current;
    }
}

注意有错别字

    node *node = (node*)malloc(sizeof(node));

此声明中变量节点的名称隐藏了声明结构的typedef名称节点。

Answer 3

使用递归反转列表会导致超长列表出现栈溢出错误

您可以在不递归且不分配任何额外内存的情况下反转列表，只需遍历列表并将每个节点的 next 成员反转为指向前一个元素。

void reverse(queue* queue) {
    node* head = queue->head;
    node* tail = queue->tail;
    node* prev = queue->head;
    node* current = queue->head ? queue->head->next : NULL;
    node* next = current ? current->next : NULL;

    while (current) {
        current->next = prev;
        prev = current;
        current = next;
        next = current ? current->next : NULL;
    }

    // fix up the head and tail of the list
    queue->head = tail;
    queue->tail = head;
    if (queue->tail) {
        queue->tail->next = NULL;
    }
}

如何反转队列的链表实现

How to reverse a linked list implementation of a queue

c

struct

linked-list

reverse

function-definition

反向函数