面试题18-删除列表中的节点

题目要求

在O(1)的时间内删除链表节点给定单向链表的头和一个节点指针，定义的函数在O(1)内删除该节点。

题目解析

思路一：

• 分析

一般情况我们可以采用从头结点遍历的方式，得到要删除的节点i，之前的J节点，
将i的next属性值赋值给j的next属性。将i节点删除
那有没有另一种方法呢？答案是有的：
得到i的next值为K，将k的值复制到i的value属性，将k的next属性值复制到i的next属性。
但是如果，要删除的节点为尾节点没有下一个节点，那么只能采取从头结点遍历，的第一种方法。
还需注意，如果删除的链表里只有一个元素，那么删除完毕之后将链表清空。
编程过程忽略了检验删除元素是否存在在链表中，因为要达到O（1）,检验过程交给方法使用者来处理。

• 代码段

public static ListNode deleteListNode(ListNode head , ListNode deleteNode) {
        
        //如果要删除的节点就是头结点
        if(head==deleteNode) {
            return head.getNext() ;
        }
        
        //如果删除节点不是尾节点那么可以用复制后面节点内容的方法。
        if( deleteNode.getNext() != null ) {
            
            ListNode after = deleteNode.getNext() ;
            deleteNode.setValue(after.getValue());
            deleteNode.setNext(after.getNext());
            return head;
        }
        
        //如果是尾节点那么需要从头结点遍历
        while( head != null ) {
            if(head.getNext() == deleteNode) {
                break ;
            }
            head = head.getNext() ;
        }
        head.setNext(deleteNode.getNext());
        
        return head ;
    }

测试代码

    //测试代码
    public static void main(String[] args) {
        
        ListNode node1 = new ListNode() ;
        ListNode node2 = new ListNode() ;
        ListNode node3 = new ListNode() ;
        ListNode head = null ;
        
        node1.setValue(1);
        node2.setValue(2);
        node3.setValue(3);
        
        node1.setNext(node2);
        node2.setNext(node3);
        showListNode(node1) ;
        head = deleteListNode(node1, node2) ;
        showListNode(head) ;
        head = deleteListNode(head, node2) ;
        showListNode(head) ;
        head = deleteListNode(head, node1) ;
        showListNode(head) ;
    }

运行结果

1 2 3
1 3
1

看完整源码戳源码地址