leetcode82. Remove Duplicates from Sorted List II

崔曉明發(fā)布于2019-08-15 10:36 / 2800人閱讀

摘要：題目要求翻譯將鏈表中重復(fù)的元素全部刪除，返回新的頭結(jié)點。相比于，這里將重復(fù)的元素全部刪除。除此以外，我們還需要知道重復(fù)元素的前一個值和重復(fù)元素的最后一個值。如果存在重復(fù)值，則跳過重復(fù)值后，前節(jié)點不變，否則前節(jié)點跟隨后節(jié)點同時向后移動。

題目要求

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

翻譯：將鏈表中重復(fù)的元素全部刪除，返回新的頭結(jié)點。

相比于Remove Duplicates from Sorted List I，這里將重復(fù)的元素全部刪除。
想要了解Remove Duplicates from Sorted List I，請參考我的這篇博客

思路和代碼

這里，我們首先需要一個偽頭節(jié)點指向當(dāng)前的頭節(jié)點，以確保我們最后能夠找到結(jié)果集的頭節(jié)點。除此以外，我們還需要知道重復(fù)元素的前一個值和重復(fù)元素的最后一個值。
舉個例子：如果數(shù)組元素為[1，2，2，3]，那么我們需要知道1這個節(jié)點和3這個節(jié)點的位置，并將1的下一個節(jié)點指向3。特殊情況，如[1,1,2,2]，這是我們就可以將偽頭結(jié)點作為我們的前節(jié)點，并將2作為我們的后節(jié)點。如果存在重復(fù)值，則跳過重復(fù)值后，前節(jié)點不變，否則前節(jié)點跟隨后節(jié)點同時向后移動。代碼如下：

    public ListNode deleteDuplicates(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode start = new ListNode(0);
        start.next = head;
        ListNode prevNode = start;
        ListNode current = head;
        while(current != null){
            if(current.next != null && current.val == current.next.val){
                do{
                    current = current.next;
                }while(current.next != null && current.val == current.next.val);
                prevNode.next = current.next;
            }else{
                prevNode = current;
            }
            current = current.next;
        }
        return start.next;
    }
    
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x;}
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~