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

朴灿烈づ我的快乐病毒、 2023-10-09 13:45 36阅读 0赞

#### 文章目录 ####

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

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

### 描述 ###

以前在单链表中我们删除一个结点，需要我们定义一个指针p来遍历整个链表，找到待删结点的前一个结点，使当前节点的next域指向待删结点的下一个结点，完成删除指定结点。如下图：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]

我们考虑一下这样的时间复杂度是多少呢？需要遍历整个链表，所以平均时间复杂度为O(n)。那么怎么才能在O(1)时间复杂度下删除一个指定结点呢？我们可以把当前节点的value值改为下一个结点，然后使当前节点的next域指向下下个结点。注意：指定的结点不能是链表中的最后一个结点，如果是链表中的最后一个结点，需要遍历整个链表。

### 图示 ###

![在这里插入图片描述][2e5535690ab34091a7f41df52ca06d78.gif]

### 代码 ###

/**
     * 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;
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAV1lTQ09ERVI_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/b8b6d5fb7949428fa09dcd1fa1a9d1d9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAV1lTQ09ERVI=,size_20,color_FFFFFF,t_70,g_se,x_16
[2e5535690ab34091a7f41df52ca06d78.gif]: https://img-blog.csdnimg.cn/2e5535690ab34091a7f41df52ca06d78.gif