单链表删除这个节点？对于单向链表，每个节点的数据结构除了要存储自己的数据外，还需要记录下一个节点在链表上的地址。通常我们称这个地址为后续指针next。如上图，我想删除C节点，需要做什么？很简单，只要将B节点的后续指针next指向D节点即可。这里应该清楚了，要删除链表上的一个节点，我们需要知道三个节点：要删除的节点。待删除节点的前驱节点。要删除的节点的后继节点。思路：其实删掉下一个节点，然后复习原题。当我们知道某个节点时，我们也知道它的后续节点。唯一的问题是我们不知道他的前任节点。最简单的解决办法就是遍历链表，获取待删除节点的前驱节点，对其进行操作。说到遍历链表，时间复杂度妥妥的变成了O(n)，与题中不符。主要问题是我们如何知道要删除的节点的前驱节点。试着换个角度想，我们只需要删除节点中存储的数据，而不是节点对应地址中的内容。然后将待删除节点的数据与其后续节点的数据进行交换，再将后续节点删除，从而实现时间复杂度为O(1)的单链表删除。问题：要删除的节点是最后一个节点的思路还是有问题。我们真正删除的是要删除的节点的下一个节点。还记得我前面说的删除单向链表中的一个节点，其实你需要知道三个节点。那么，如果删除的节点是单向链表的最后一个节点怎么办？这时候我们还需要从链表的头节点开始遍历，得到要删除的节点的前驱节点，完成删除操作。复杂度返回到O(n)。题目要求我们需要在O(1)的时间复杂度内完成删除操作。这不符合题主的要求吗？事实上，并非如此。假设单向链表一共有n个节点，这个算法在n-1的情况下时间复杂度是O(1)，并且只有当要删除的节点是单向链表的最后一个节点时，时间复杂度会回到O(n)，那么平均时间复杂度[(n-1)*O(1)+O(n)]/n，计算还是O(1)。【本文为专栏作家“张扬”原创稿件，转载请微信♂联系作者获得授权】点此查看作者更多好文
