如何删除单链表中给定位置的节点？

Question

我一直在尝试创建一个函数，在给定特定位置时删除节点。如果位置超出范围，则会显示一条消息，而不是应删除该节点。

我尝试过 if/else 语句、for 循环、while 循环。我知道该函数的一部分是有效的，因为我已经做了一些测试。我知道当该位置位于头部时，该节点将被删除，但是当给出任何其他位置时，即使该节点存在于该位置，它仍然显示出范围消息。

template<class Type>
void linkedListType<Type>::removeAt(int location)
{
    nodeType<Type> *current;
    nodeType<Type> *trailCurrent;
    current = first;
    int counter;

    if (location < 0 || location >= count)
    {
        cout << "location out of range\n";
    }
    else if(location == 0)
    {
        first = first->link;
        if (first == NULL)
            last == NULL;
        delete current;
    }
    else 
    {
        counter = 0;
   
        while (counter != location - 1)
        {
            current = current->link;
            counter++;
        }

        trailCurrent = current->link;
        current->link = trailCurrent->link;
        delete current;
    }
}

Answer 1

您已经

last == NULL;

到达您想要的

last = NULL;

。

缺少什么：

--count;

。

该算法还可以使用 aliasing，使用 first 或

link

字段的

address

。

... checks on count ...
nodeType<Type>*& a = first;
while (location > 0) {
    --location;
    a = a->link;
}
nodeType<Type>* dead = a;
a = a.link;
deleted dead;

在 C 风格中发生的事情更加清晰：

nodeType<Type>** a = & first;
while (location > 0) {
    --location;
    a = &(*a)->link;
}
nodeType<Type>* dead = *a;
*a = (*a).link;
deleted dead;