本文主要是介绍10 在O(1)时间删除链表节点:给定单向链表的一个头指针和节点指针，定义一个函数在O(1)时间删除该节，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目
给定单向链表的一个头指针和节点指针，定义一个函数在O(1)时间删除该节点。
二、解题思路
由于给定了节点指针，那么要删除该节点。只要把该节点的值替换为下一个节点的值，同时让该节点直接指向下一个节点的下一个节点。相当于顶包代替了下一个节点，该节点自然就不存在。
需要注意的是如果指定节点是头结点，那么直接把头结点定义为下一个节点即可。如果是尾节点，需要循环遍历到该节点，然后让尾节点的上一个节点的指针为空即可。
如果删除的结点位于链表的尾部，没有下一个结点，怎么办？我们仍然从链表的头结点开始，顺便遍历得到给定结点的前序结点，并完成删除操作。这个时候时间复杂度是O(n)。那题目要求我们需要在O(1)时间完成删除操作，我们的算法是不是不符合要求？实际上，假设链表总共有n个结点，我们的算法在n-1总情况下时间复杂度是O(1)，只有当给定的结点处于链表末尾的时候，时间复杂度为O(n)。那么平均时间复杂度[(n-1)*O(1)+O(n)]/n来源：CSDN
原文：https://blog.csdn.net/danielzhou888/article/details/83627014
--------------------- --------------------- --------------------- --------------------- public static ListNode delete(ListNode head ,ListNode toBeDeleted){if(head==null||toBeDeleted==null) {return null;}if(head==toBeDeleted) {return head.next;}//最后一个if(toBeDeleted.next==null) {ListNode temp=head;while (temp.next!=toBeDeleted){temp=temp.next;}//删除节点temp.next=null;}else {//中间节点 让给节点的下一个节点顶包被删除toBeDeleted.value=toBeDeleted.next.value;toBeDeleted.next=toBeDeleted.next.next;}return head;} 这篇关于10 在O(1)时间删除链表节点:给定单向链表的一个头指针和节点指针，定义一个函数在O(1)时间删除该节的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
