Java 单链表在O(1)时间复杂度下删除一个指定结点

本文主要是介绍Java 单链表在O(1)时间复杂度下删除一个指定结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

单链表在O(1)时间复杂度下删除一个指定结点
- 描述
- 图示
- 代码

单链表在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;}
}