前言有一个单向链表，给定一个头指针和一个节点指针，如何在O(1)时间内删除节点？本文将分享一个解决该问题的实现思路，欢迎有兴趣的开发者阅读本文。思路分析在单向链表中，如果要删除一个结点，首先想到的是：从链表的头结点开始，依次遍历找到要删除的结点，将找到后完成节点删除的指针。遍历链表并删除节点下面我们以一个链表为例，删除节点10，则删除过程如下图所示：从链表头部开始沿着指针遍历，发现节点9的指针指向节点10（待删除的节点）获取节点10的指针指向的节点13，修改节点9的指针指向节点13，节点10的删除完成。这样，我们确实删除了给定的节点，但是我们需要从头开始遍历链表寻找节点，时间复杂度为O(n)。如果达不到题目的要求，这种方法是行不通的。覆盖节点，实现删除接下来我们换个思路。既然最耗时的地方就是遍历找节点，那我们就不遍历了，充分利用题中给出的条件来进一步思考。再次复习题目，发现它给出了一个指向待删除节点的指针，那么我们就可以得到指针指向的值。有了这个值，我们就可以：覆盖和修改指向要删除节点的值的指针，删除下一个节点，我们继续使用上一章给出的例子。其执行过程如下图所示：注意：当待删除节点的下一个节点值是最后一个时，我们只需要将待删除节点的指针指向null即可。如果下一个节点之后还有节点，那么我们只需要获取该节点，并将其指针指向获取到的节点即可，如下图：image-20220210213628642通过以上思路，我们在O(1)时间内删除给定节点，但是还有一个问题：如果要删除的节点在链表的尾部，那么它就没有下一个节点了，此时我们不能使用这个方法，只能依次遍历得到node的前一个节点，并完成删除操作。时间复杂度分析：对于n-1个非尾节点，我们可以使用节点覆盖的方法在O(1)时间内删除，但是对于尾节点，我们仍然需要遍历才能删除节点，时间复杂度为O(n).那么，总的时间复杂度就是：[(n-1)*O(1)+O(n)]/n，最后的结果还是O(1)，符合题目要求。如果链表中只有一个节点，而我们要删除链表的头节点（也是尾节点），那么我们需要在删除节点后将链表的头节点设置为null。有了实现代码的思路后，我们就可以愉快的编写代码了，如下图：当链表只有一个节点时，直接返回nul，调用者删除链表的头节点，待删除的节点没有下一个节点，则遍历寻找上一个节点，将指针指向null，使用覆盖节点的方法删除节点类型ListNode={element:number;下一页：ListNode|无效的};导出类DeleteLinkedListNode{deleteNode（listHead：ListNode，toBeDeleted：ListNode）：ListNode|null{//当链表只有一个节点时，返回nullif(listHead.next==null){returnnull;}//当要删除的节点在末尾时，依次遍历Node实现deleteif(toBeDeleted.next==null){letcurNode=listHead.next;//找到要删除的节点的前一个节点while(curNode.next!=null&&curNode.next.element!==toBeDeleted.element){curNode=curNode.next;}//前一个节点已经找到，只需将其指针设置为空curNode.next=null;返回列表头；}//如果要删除的节点后面还有节点，则采用覆盖的方式来达到删除的目的//将要删除的节点的值改为下一个节点的值toBeDeleted.element=toBeDeleted.下一个元素；//待删除节点的指针指向下一个节点toBeDeleted.next=toBeDeleted.下一个。下一个；返回列表头；}}TestCase最后，我们使用上一章给出的例子来验证代码是否可以正确执行。从“../DeleteLinkedListNode.ts”导入{DeleteLinkedListNode}；从“../lib/LinkedList.ts”导入LinkedList；constlistNode=newLinkedList()；listNode.push(3)；listNode.push(5)；listNode.push(7);listNode.push(9);listNode.push(10);listNode.push(13);listNode.push(15);constdeleteLinkedListNode=newDeleteLinkedListNode();//获取链表头pointerandPointertonode10constresult=deleteLinkedListNode.deleteNode(listNode.getHead(),listNode.getElementAt(4));if(result==null){//删除链表的头节点listNode.removeAt(0）;}安慰。log("删除节点10后，链表剩余节点为：",listNode.toString());运行结果如下：上面代码中的LinkedList类是自己实现的，对此感兴趣的开发者请移步：链表与伪装链表的实现[1]。示例代码本文示例的完整代码如下：DeleteLinkedListNode.ts[2]deleteLinkedListNode-test.ts[3]LinkedList.ts[4]写在最后，分享给大家。我是魔法程序员，前端开发工程师。如果你对我感兴趣，请到我的个人网站[5]了解更多。文章如有错误，欢迎在评论区指正。如果本文对您有帮助，请点赞关注
