[剑指Offer]-删除链表节点
题目描述
请编写一个函数,使其可以删除某个链表中给定的节点,您将只被给予要求被删除的节点。
所以实现的思路是,根据给定的要删除的节点,可以直接找到其后年的节点,把后面的节点的内容复制到当前节点处,同时将当前节点指向其后面节点的后面节点保证链表不断开,再把下一节点删掉就相当于把给定的节点删除了。
解题思路
- 将要删除的节点的下一个节点直接覆盖到当前节点,然后删除掉下一个节点。
算法图解
参考代码:
package offer;
/**
* 删除链表节点 删除的节点信息复制到前一个节点 然后删除该节点
*/
public class Offer18 {
public static void main(String[] args) {
LinkNode<Integer> firstNode = new LinkNode<Integer>();
LinkNode<Integer> node2 = new LinkNode<Integer>();
LinkNode<Integer> node3 = new LinkNode<Integer>();
LinkNode<Integer> node4 = new LinkNode<Integer>();
LinkNode<Integer> node5 = new LinkNode<Integer>();
firstNode.next = node2;
firstNode.node_value = 1;
node2.next = node3;
node2.node_value = 2;
node3.next = node4;
node3.node_value = 3;
node4.next = node5;
node4.node_value = 4;
node5.node_value = 5;
node5.next = null;
DeleteNode(firstNode, node5);
}
/**
* 头节点 尾节点 任意位置 三种情况
*
* @param firstNode 链表
* @param ToBedelete 需要被删除的
*/
private static void DeleteNode(LinkNode<Integer> firstNode, LinkNode<Integer> ToBedelete) {
if (firstNode == null || ToBedelete == null) {
return;
}
/**
* 头尾
*/
if (ToBedelete == firstNode) {
System.out.println("删除头"+firstNode.node_value);
firstNode = null;
return;
}
/**
* 不是尾节点
*/
System.out.println("删除非头尾"+ToBedelete.node_value);
if (ToBedelete.next != null) {
LinkNode<Integer> nextNode = ToBedelete.next;
ToBedelete.node_value = nextNode.node_value;
ToBedelete.next = nextNode.next;
ToBedelete.next = null;
} else {
LinkNode pointNode = firstNode;
while (pointNode.next != ToBedelete) {
pointNode = pointNode.next;
}
System.out.println("删除尾"+pointNode.next.node_value);
pointNode.next = null;
}
}
}
/**
* 模拟链表数据结构
*
* @param <E>
*/
class LinkNode<E> {
LinkNode<Integer> next;
E node_value;
}
附录
该题源码在我的 ????Github 上面!