[剑指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 上面！