面试题18-1:O(1)时间内删除链表的节点

package cn.zxy.interview;


import cn.zxy.interview.utils.ListNode;
import cn.zxy.interview.utils.UtilsLinkedList;
import org.junit.Test;

/**
 * 给定头结点的引用和要删除的节点对象的引用, 在O(1)时间内删除一个节点
 * 删除节点的一般思路是从头指针开始遍历, 遍历过程维护一个preNode, 当pNode==delNode时, 令preNode.next = pNode.next
 * 这样的时间复杂度是O(n)
 *
 * 另一种思路, 用下一节点的值覆盖掉要删除节点的值
 *
 * 特殊情况, 下一节点没有值, 也就是删除的元素是尾结点, 依然需要遍历
 *
 *这样均摊时间复杂度仍然是O(1)
 *
 * ps 由于Java通过传递不能改变引用本身, 也就是说root作为参数传入后, 不能进行这样的操作root=某个node的引用
 *      因此, 在java中通常使用一个value位为空的节点对象作为头指针, 这样每个元素都可以通过前一个元素的next得到, first通过root的next的得到
 *      这样处理后, 当对首元素进行操作时, 也不需要单独处理
 *
 * 在书中的C++代码中, 头指针直接指向首元素, 当操作首元素时, 就需要就需要单独处理了
 */

public class A18_DeleteNode {
    @Test
    public void main(){
        //1.创建链表 返回链表根节点
        ListNode root = UtilsLinkedList.build();
        //2.输入元素的值, 返回引用
        ListNode oneNode = UtilsLinkedList.findOneNode(root, 10);
        //3.删除之前打印
        UtilsLinkedList.showList(root);
        System.out.println();
        //4.删除指定节点
        deleteNode(root, oneNode);
        //5.删除后展示
        UtilsLinkedList.showList(root);


    }

    public void deleteNode(ListNode root, ListNode delNode) {
        //非法输入: 头引用或待删除引用为null, 直接返回

        //要删除的节点不是尾结点
        if(delNode.next != null){
            ListNode delNextNode = delNode.next;
            delNode.value = delNextNode.value;
            delNode.next = delNextNode.next;
        }else{
            ListNode node = root.next;
            while(node.next != delNode){
                node = node.next;
            }
            // 循环退出后, node.next == delNode 即node指向要删除节点的前一个
            // 将该节点next置为null即可
            node.next = null;
        }
    }

}

用到的链表生成工具类

package cn.zxy.interview.utils;

public class UtilsLinkedList {
    /**
     * 生成链表, 返回链表的头节点引用
     * @return
     */
    public static ListNode build(){
        ListNode root = new ListNode();
        root.next = null;

        int listLength = 10;
        for (int i = listLength; i >= 1; i--) {
            // 头插法
            ListNode node = new ListNode();
            node.value = 10 * i;
            node.next = root.next;
            root.next = node;
        }
        return root;
    }

    /**
     * 输入链表元素的值, 返回对应节点对象的引用
     */
    public static ListNode findOneNode(ListNode root, int value){
        if(root == null) return null;

        ListNode theNode = null;
        ListNode node = root.next;
        while(node != null){
            if(node.value == value){
                theNode = node;
                break;
            }
            node = node.next;
        }
        return theNode;
    }

    public static void showList(ListNode root){
        ListNode node = root.next;
        while (node != null){
            System.out.print(node.value + "  ");
            node = node.next;
        }
        System.out.println();
    }

    /**
     * 生成有重复元素的链表
     * @return
     */
    public static ListNode buildRepeat(){
        ListNode root = new ListNode();
        root.next = null;

        int listLength = 10;
        int value;
        for (int i = listLength; i >= 1; i--) {
            // 头插法
            if(i >= 1 && i <= 5) {
                value = 50;  // 将元素50重复3次
            }else if(i>=6 && i <= 7) {
                value = 60;
            }else{
                    value = 10 * i;
            }


            ListNode node = new ListNode();
            node.value = value;
            node.next = root.next;
            root.next = node;
        }
        return root;
    }

}

链表节点定义

package cn.zxy.interview.utils;

public class ListNode {
    public int value;
    public ListNode next;

    public ListNode() {
    }

    public ListNode(int value, ListNode next) {
        this.value = value;
        this.next = next;
    }
}