文章目录
单链表在O(1)时间复杂度下删除一个指定结点
描述
以前在单链表中我们删除一个结点，需要我们定义一个指针p来遍历整个链表，找到待删结点的前一个结点，使当前节点的next域指向待删结点的下一个结点，完成删除指定结点。如下图：
我们考虑一下这样的时间复杂度是多少呢？需要遍历整个链表，所以平均时间复杂度为O(n)。那么怎么才能在O(1)时间复杂度下删除一个指定结点呢？我们可以把当前节点的value值改为下一个结点，然后使当前节点的next域指向下下个结点。注意：指定的结点不能是链表中的最后一个结点，如果是链表中的最后一个结点，需要遍历整个链表。
图示
代码
/**
* Definition for singly-linked list.
* public class Node {
* int val;
* Node next;
* Node() {}
* Node(int val) { this.val = val; }
* Node(int val, Node next) { this.val = val; this.next = next; }
* }
*/
class SingleLink {
Node head;//标记链表头部
Node tail;//标记链表尾部
public void removeNode(Node node) {
//链表为空
if (head == null) {
return;
}
//链表长度为1 且是待删除结点
if(head.next == null && head = node) {
head = null;
}
//当前节点的val值改为下一个结点的value值，然后使当前节点的next域指向下下个结点
node.val = node.next.val;
node.next = node.next.next;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/95552.html
