单链表如何设计在 O(1)时间删除单链表节点

题目描述

提供单链表的首节点和删除节点，定义一个方法在 O(1)时间删除该节点。

思路分析

常规的做法是从链表的首节点开始遍历，找到需要删除的节点的前驱节点，把它的 next 指向要 删除节点的下一个节点，平均时间复杂度为 O(n)，不满足题目要求

那是不是一定要得到被删除的节点的前一个节点呢？其实不用的。我们可以很方面地得到要删 除节点的下一个节点，如果我们把下一个节点的内容复制到要删除的节点上覆盖原有的内容，再把 下一个节点删除，那就相当于把当前要删除的节点删除了。举个栗子，我们要删除的节点 i，先把 i 的下一个节点 j 的内容复制到 i，然后把 i 的指针指向节点 j 的下一个节点。此时再删除节点 j，其效 果刚好是把节点 i 给删除了。

节点类

@Data
public class Node {
/**
* 用于保存节点中的数据
*/
private Object data;
/**
* 用于保存下一个节点的地址值
*/
private Node next;

public Node(Object data) {
this.data = data;
}

public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
}

实现类

package day04;

/**
* @Author yqq
* @Date 2022/05/07 12:32
* @Version 1.0
*/
public class Test01 {
public static void main(String[] args) {
Node lastNode = new Node(55);
Node node4 = new Node(44,lastNode);
Node node3 = new Node(33,node4);
Node node2 = new Node(22,node3);
Node headNode = new Node(11,node2);
Node node = delete(headNode, lastNode);
print(node);
}

/**
* 实现单链表的遍历操作
* @param headNode
*/
public static void print(Node headNode){
//定义一个临时节点，用于辅助单链表的遍历操作
Node tempNode = headNode;
//定义一个循环，泳用于实现单链表的遍历操作
while (tempNode != null){
//输出tempNode中data值
System.out.println(tempNode.getData());
//让tempNode指向下一个节点
tempNode = tempNode.getNext();
}
}

/**
* 在O(1)时间删除单链表节点
* @param headNode 首节点
* @param delNode 删除节点
* @return
*/
public static Node delete(Node headNode,Node delNode){
//处理headNode为null和delNode为null的情况
if (headNode == null || delNode == null)
throw new NullPointerException("headNode 或 delNode为null");
//处理删除节点在开头的情况
if (headNode == delNode){
//获得删除节点的后一个节点
Node nextNode = headNode.getNext();
//设置headNode的next为null
headNode.setNext(null);
//返回删除节点的后单链表的首节点
return nextNode;
}
//处理删除节点在结尾的情况
else if (delNode.getNext() == null){
//获得删除节点的前一个节点
//定义一个临时节点，用于辅助遍历链表
Node tempNode = headNode;
//定义一个循环，用于找到尾结点的前一个节点
while (tempNode.getNext() != delNode){
//让tempNode指向它的下一个节点
tempNode = tempNode.getNext();
}
//设置tempNode的next为null
tempNode.setNext(null);
//返回删除节点后单链表的首节点
return headNode;
}
//处理删除节点在中间任意位置的情况
else {
//获得删除节点的后一个节点
Node nextNode = delNode.getNext();
//把nextNode中保存的数据赋值给删除节点
delNode.setData(nextNode.getData());
//从单链表中删除nextNode
//设置delNode的next值为nextNode的下一个节点
delNode.setNext(nextNode.getNext());
//设置nextNode的next为null
nextNode.setNext(null);
//返回删除节点后单链表的首节点
return headNode;
}
}
}