題目要求

在O(1)的時間內(nèi)刪除鏈表節(jié)點給定單向鏈表的頭和一個節(jié)點指針，定義的函數(shù)在O(1)內(nèi)刪除該節(jié)點。

題目解析

思路一：

• 分析

一般情況我們可以采用從頭結(jié)點遍歷的方式，得到要刪除的節(jié)點i，之前的J節(jié)點，
將i的next屬性值賦值給j的next屬性。將i節(jié)點刪除
那有沒有另一種方法呢？答案是有的：
得到i的next值為K，將k的值復(fù)制到i的value屬性，將k的next屬性值復(fù)制到i的next屬性。
但是如果，要刪除的節(jié)點為尾節(jié)點沒有下一個節(jié)點，那么只能采取從頭結(jié)點遍歷，的第一種方法。
還需注意，如果刪除的鏈表里只有一個元素，那么刪除完畢之后將鏈表清空。
編程過程忽略了檢驗刪除元素是否存在在鏈表中，因為要達(dá)到O（1）,檢驗過程交給方法使用者來處理。

• 代碼段

public static ListNode deleteListNode(ListNode head , ListNode deleteNode) {
        
        //如果要刪除的節(jié)點就是頭結(jié)點
        if(head==deleteNode) {
            return head.getNext() ;
        }
        
        //如果刪除節(jié)點不是尾節(jié)點那么可以用復(fù)制后面節(jié)點內(nèi)容的方法。
        if( deleteNode.getNext() != null ) {
            
            ListNode after = deleteNode.getNext() ;
            deleteNode.setValue(after.getValue());
            deleteNode.setNext(after.getNext());
            return head;
        }
        
        //如果是尾節(jié)點那么需要從頭結(jié)點遍歷
        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) ;
    }

運行結(jié)果

1 2 3
1 3
1

看完整源碼戳源碼地址