删除循环双向链表时我不满足哪个条件？

Question

这是我的删除函数。

void removeAt (int pos)
{
    struct Node *temp= (struct Node *) malloc(sizeof(struct Node *)); 
    struct Node *x=(struct Node *)malloc(sizeof(struct Node *));

if(pos==1)
{
if(head==tail)

{ 
    temp=head;
    head=tail=NULL; 
    free (temp);
}

else
{

temp=head;
head=head->next;

head->prev=tail;
tail->next=head;

free (temp);
}
}

else
{

    temp=NULL;
    for(int i=0;i<pos;i++)
    { 
        x=temp; 
        if(i==0)
        temp=head;

        else
        temp=temp->next;
    }

    x->next=temp->next;

    if(temp==tail)
    x->next=head;
    else
    temp->next->prev=x; 
    free (temp);

}

}

此函数将输入作为位置并删除该位置的元素。当我运行时，我正在获取私人测试用例失败。我无法弄清楚我未能满足哪个测试用例。请帮我解决这个问题。

Answer 1

有几个重大问题。首先，由于您正在删除节点，我希望看到 free 语句但没有 malloc 语句。

关于台词：

struct Node *temp= (struct Node *) malloc(sizeof(struct Node *)); 
struct Node *x=(struct Node *)malloc(sizeof(struct Node *));

指针 x 和 temp 应保持未初始化状态或设置为 NULL。

在条件 if(pos==1) / if(head==tail) 下，你只有一个节点，所以你基本上会释放头部并将 head 和 tail 指针都设置为 NULL.

在条件 if(pos==1) / else 下，您的代码应该按原样工作。

在条件 else 下，从零开始 for 循环没有意义，因为该位置实际上永远不可能为零，而且这需要额外的条件语句。但是，如果 pos 设置为零，您将取消引用 Null 指针，这会导致异常。另外，我不确定为什么需要这个条件：

if(temp==tail)
    x->next=head;

Answer 2

一些问题：

不分配内存：该函数不会添加任何节点，因此该内存没有任何作用，实际上会泄漏。
head->tail 是无效引用。在你有这条线的地方，你应该设置 head = tail = NULL;
if(temp==tail) x->next=head;：因为你的列表是循环的，它应该总是有 tail->next == head，所以不需要这个分配。
temp->next->prev=x; 应该总是被执行，当 temp == tail 时也是如此。由于列表是循环的，因此 tail 节点在设置 prev 或 next.
时不需要特殊处理
删除 tail 节点后，没有代码可以调整 tail 引用。
由于列表是循环的，因此不需要区分pos==1和其他列表。需要注意的特殊情况是：
- 当列表为空时，该函数不应执行任何操作。
- 当列表只有一个节点时，应该将其清空。
- 如果 head 节点被删除，head 引用应该被更新（就像你做的那样）
- 如果删除 tail 节点，则应更新 tail 引用

这是更正后的代码：

void removeAt(int pos) {
    // Safeguard
    if (head == NULL || pos <= 0) return;

    // Don't allocate node memory with malloc
    struct Node *temp = head;
    if (head == tail) {
        head = tail = NULL; // fix
    } else { 
        for (int i = 1; i < pos; i++) { 
            temp = temp->next;
        }
        temp->prev->next = temp->next;
        temp->next->prev = temp->prev;
        if (temp == tail) tail = temp->prev;
        head = tail->next;  // Invariant
    }
    free(temp);
}

删除循环双向链表时我不满足哪个条件？

Which condition I'm failing to satisfy in removing circular doubly linked list?

c

linked-list

structure

circular-list