題目要求

刪除鏈表中重復(fù)的節(jié)點(diǎn)。
重復(fù)的節(jié)點(diǎn)：
當(dāng)前節(jié)點(diǎn)的值與下一個(gè)節(jié)點(diǎn)的值相等，那么稱這兩個(gè)節(jié)點(diǎn)為重復(fù)的節(jié)點(diǎn)

題目解析

思路一：

• 分析

假設(shè)該鏈表為2、3、3、4、4、5
刪除完畢之后變?yōu)?、5
那么如果是2、2、5、6
刪除完畢之后成為5、6。這個(gè)時(shí)候需要改變頭結(jié)點(diǎn)，所以我們必須返回新的頭結(jié)點(diǎn)
另外還需要考慮的是如果是2、2、2
那么刪除完畢之后，鏈表為空。
情況分析完畢，現(xiàn)在我們來看如何對(duì)重復(fù)的節(jié)點(diǎn)進(jìn)行刪除。
首先從頭結(jié)點(diǎn)開始遍歷，檢查當(dāng)前節(jié)點(diǎn)的值curValue是否與下一個(gè)節(jié)點(diǎn)的值相等。如果相等繼續(xù)檢查再下一個(gè)節(jié)點(diǎn)是否相等。
直到發(fā)現(xiàn)不相等的，將最后一個(gè)相等的節(jié)點(diǎn)的next值賦給第一個(gè)相等的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的next。
如果head節(jié)點(diǎn)就是相等的節(jié)點(diǎn)，那么我們?cè)趧h除以后要注意改變鏈表的頭結(jié)點(diǎn)。

• 代碼段

public static ListNode deleteRepeatNode(ListNode head) {
        
        //定義一個(gè)輔助節(jié)點(diǎn)記錄刪除區(qū)間的前一個(gè)節(jié)點(diǎn)
        ListNode preNode = null ;
        //定義一個(gè)輔助節(jié)點(diǎn)記錄頭結(jié)點(diǎn)
        ListNode headNode = head ;
        //定義一個(gè)輔助標(biāo)記是否有重復(fù)的節(jié)點(diǎn)
        boolean hasRepeat = false ;
        
        //判空
        if(head == null) {
            return headNode ;
        }
        
        
        //從head開始往尾節(jié)點(diǎn)遍歷
        while( head != null && head.getNext() != null) {
            
            //遍歷有多少個(gè)重復(fù)的節(jié)點(diǎn)
            while( head.getNext() != null && head.getValue() == head.getNext().getValue()) {
                head = head.getNext() ;
                hasRepeat = true ;
            }
            
            if (hasRepeat) {
                //如果存在了重復(fù)的節(jié)點(diǎn),那么進(jìn)行刪除處理
                if(preNode == null) {
                    headNode = head.getNext() ;
                }else {
                    preNode.setNext(head.getNext());
                }
            }else {
                //如果不存在，記錄當(dāng)前不存在的節(jié)點(diǎn)，作為preNode ;
                preNode = head ;
            }
            
            head = head.getNext() ;
            
        }
        
        return headNode ;
    }

測(cè)試代碼

public static void main(String[] args) {
        
        ListNode node1 = new ListNode() ;
        ListNode node2 = new ListNode() ;
        ListNode node3 = new ListNode() ;
        ListNode node4 = new ListNode() ;
        ListNode node5 = new ListNode() ;
        ListNode head = null ;
        
        node1.setValue(1);
        node2.setValue(1);
        node3.setValue(3);
        node4.setValue(3);
        node5.setValue(5);
        
        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        
        head = deleteRepeatNode(node1) ;
        showListNode(head);
        
        node1.setValue(1);
        node2.setValue(2);
        node3.setValue(3);
        node4.setValue(4);
        node5.setValue(5);
        
        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        
        head = deleteRepeatNode(node1) ;
        showListNode(head);
        
        node1.setValue(1);
        node2.setValue(1);
        node3.setValue(1);
        node4.setValue(1);
        node5.setValue(1);
        
        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        
        head = deleteRepeatNode(node1) ;
        showListNode(head);
        
        ListNode nullNode = null ;
        head = deleteRepeatNode(nullNode) ;
        showListNode(head);
        
    }

運(yùn)行結(jié)果

5
1 2 3 4 5

看完整源碼戳源碼地址