刪除鏈表中重復(fù)的結(jié)點(diǎn)

題目：在一個排序的鏈表中，如何刪除重復(fù)的結(jié)點(diǎn)？

解題思路

解決這個問題的第一步是確定刪除的參數(shù)。當(dāng)然這個函數(shù)需要輸入待刪除鏈表的頭結(jié)點(diǎn)。頭結(jié)點(diǎn)可能與后面的結(jié)點(diǎn)重復(fù)，也就是說頭結(jié)點(diǎn)也可能被刪除，所以在鏈表頭添加一個結(jié)點(diǎn)。

接下來我們從頭遍歷整個鏈表。如果當(dāng)前結(jié)點(diǎn)的值與下一個結(jié)點(diǎn)的值相同，那么它們就是重復(fù)的結(jié)點(diǎn)，都可以被刪除。為了保證刪除之后的鏈表仍然是相連的而沒有中間斷開，我們要把當(dāng)前的前一個結(jié)點(diǎn)和后面值比當(dāng)前結(jié)點(diǎn)的值要大的結(jié)點(diǎn)相連。我們要確保prev要始終與下一個沒有重復(fù)的結(jié)點(diǎn)連接在一起。

結(jié)點(diǎn)定義

private static class ListNode {
    private int val;
    private ListNode next;
    public ListNode() {
    }
    public ListNode(int val) {
        this.val = val;
    }
    @Override
    public String toString() {
        return val + "";
    }
}

代碼實(shí)現(xiàn)

public class Test57 {
    private static class ListNode {
        private int val;
        private ListNode next;
        public ListNode() {
        }
        public ListNode(int val) {
            this.val = val;
        }
        @Override
        public String toString() {
            return val + "";
        }
    }
    private static ListNode deleteDuplication(ListNode head) {
        // 為null
        if (head == null) {
            return null;
        }
//        // 只有一個結(jié)點(diǎn)
//        if (head.next == null) {
//            return head;
//        }
        // 臨時的頭結(jié)點(diǎn)
        ListNode root = new ListNode();
        root.next = head;
        // 記錄前驅(qū)結(jié)點(diǎn)
        ListNode prev = root;
        // 記錄當(dāng)前處理的結(jié)點(diǎn)
        ListNode node = head;
        while (node != null && node.next != null) {
            // 有重復(fù)結(jié)點(diǎn)，與node值相同的結(jié)點(diǎn)都要刪除
            if (node.val == node.next.val) {
                // 找到下一個不同值的節(jié)點(diǎn)，注意其有可能也是重復(fù)節(jié)點(diǎn)
                while (node.next != null && node.next.val == node.val) {
                    node = node.next;
                }
                // 指向下一個節(jié)點(diǎn)，prev.next也可能是重復(fù)結(jié)點(diǎn)
                // 所以prev不要移動到下一個結(jié)點(diǎn)
                prev.next = node.next;
            }
            // 相鄰兩個值不同，說明node不可刪除，要保留
            else {
                prev.next = node;
                prev = prev.next;
            }
            node = node.next;
        }
        return root.next;
    }
    private static void print(ListNode head) {
        while (head != null) {
            System.out.print(head + "->");
            head = head.next;
        }
        System.out.println("null");
    }
    public static void main(String[] args) {
        test01();
        test02();
        test03();
        test04();
        test05();
        test06();
        test07();
        test08();
        test09();
        test10();
    }
    // 1->2->3->3->4->4->5
    private static void test01() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(3);
        ListNode n5 = new ListNode(4);
        ListNode n6 = new ListNode(4);
        ListNode n7 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        ListNode result = deleteDuplication(n1);
        print(result);
    }
    // 1->2->3->4->5->6->7
    private static void test02() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        ListNode n6 = new ListNode(6);
        ListNode n7 = new ListNode(7);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        ListNode result = deleteDuplication(n1);
        print(result);
    }
    // 1->1->1->1->1->1->2
    private static void test03() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(1);
        ListNode n3 = new ListNode(1);
        ListNode n4 = new ListNode(1);
        ListNode n5 = new ListNode(1);
        ListNode n6 = new ListNode(1);
        ListNode n7 = new ListNode(2);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        ListNode result = deleteDuplication(n1);
        print(result);
    }
    // 1->1->1->1->1->1->1
    private static void test04() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(1);
        ListNode n3 = new ListNode(1);
        ListNode n4 = new ListNode(1);
        ListNode n5 = new ListNode(1);
        ListNode n6 = new ListNode(1);
        ListNode n7 = new ListNode(1);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        ListNode result = deleteDuplication(n1);
        print(result);
    }
    // 1->1->2->2->3->3->4->4
    private static void test05() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(1);
        ListNode n3 = new ListNode(2);
        ListNode n4 = new ListNode(2);
        ListNode n5 = new ListNode(3);
        ListNode n6 = new ListNode(3);
        ListNode n7 = new ListNode(4);
        ListNode n8 = new ListNode(4);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = n8;
        ListNode result = deleteDuplication(n1);
        print(result);
    }
    // 1->1->2->3->3->4->5->5
    private static void test06() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(1);
        ListNode n3 = new ListNode(2);
        ListNode n4 = new ListNode(3);
        ListNode n5 = new ListNode(3);
        ListNode n6 = new ListNode(4);
        ListNode n7 = new ListNode(5);
        ListNode n8 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = n8;
        ListNode result = deleteDuplication(n1);
        print(result);
    }
    // 1->1->2->2->3->3->4->5->5
    private static void test07() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(1);
        ListNode n3 = new ListNode(2);
        ListNode n4 = new ListNode(2);
        ListNode n5 = new ListNode(3);
        ListNode n6 = new ListNode(3);
        ListNode n7 = new ListNode(4);
        ListNode n8 = new ListNode(5);
        ListNode n9 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = n8;
        n8.next = n9;
        ListNode result = deleteDuplication(n1);
        print(result);
    }
    // 1->2
    private static void test08() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        n1.next = n2;
        ListNode result = deleteDuplication(n1);
        print(result);
    }
    // 1
    private static void test09() {
        ListNode n1 = new ListNode(1);
        ListNode result = deleteDuplication(n1);
        print(result);
    }
    // null
    private static void test10() {
        ListNode result = deleteDuplication(null);
        print(result);
    }
}

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

http://wiki.jikexueyuan.com/project/for-offer/images/75.png" alt="" />