牛客網高頻算法題系列-BM16-刪除有序鏈表中重複的元素-II

題目描述

給出一個升序排序的鏈表，刪除鏈表中的所有重複出現的元素，只保留原鏈表中只出現一次的元素。

原題目見：BM16 刪除有序鏈表中重複的元素-II

解法一：鏈表遍歷

首先，考慮特殊情況，如果鏈表為空或者只有一個結點，不會有重複的元素，返回原鏈表。

否則，遍歷鏈表判斷是否有重複元素，處理過程如下：

• 首先，因為頭結點也可能重複，所以使用一個虛擬頭結點dummyNode；
• 然後，用lastNonRedundantNode為上一個不重複的結點，初始化為頭結點，count記錄該結點的元素的重複次數，初始為1；
• 然後從原鏈表的第二個結點開始遍歷；
• 如果當前結點的值和lastNonRedundantNode不相同，判斷lastNonRedundantNode出現的次數，如果只出現過一次，則是一個不重複的結點，更新pre；否則不更新pre。更新lastNonRedundantNode，並將count重置為1。
• 如果當前結點的值和lastNonRedundantNode相同，則將count加1。
• 最後，判斷最後一個結點出現的次數，如果count為1，則也是不重複的結點。

最後，返回新構造的不重複元素的鏈表。

代碼

public class Bm016 {
    /**
     * 刪除有序鏈表中重複的元素-II
     *
     * @param head ListNode類
     * @return ListNode類
     */
    public static ListNode deleteDuplicates(ListNode head) {
        // 如果鏈表為空或者只有一個結點，不會有重複的元素，返回原鏈表
        if (head == null || head.next == null) {
            return head;
        }
        // 因為頭結點也可能重複，所以使用衣蛾虛擬頭結點
        ListNode dummyNode = new ListNode(-1);
        // pre未新構造的不重複元素的鏈表結點
        // lastNonRedundantNode為上一個不重複的結點
        ListNode pre = dummyNode, lastNonRedundantNode = head, next = head.next;
        // count為上一個不重複的元素的重複次數
        int count = 1;
        // 遍歷鏈表
        while (next != null) {
            // 如果當前結點的值和lastNonRedundantNode不相同，判斷lastNonRedundantNode出現的次數，如果只出現過一次，則是一個不重複的結點
            // 更新pre，否則不更新pre
            // 更新lastNonRedundantNode，並將count重置為1
            if (next.val != lastNonRedundantNode.val) {
                if (count == 1) {
                    pre.next = new ListNode(lastNonRedundantNode.val);
                    pre = pre.next;
                }
                lastNonRedundantNode = next;
                count = 1;
            } else {
                // 如果當前結點的值和lastNonRedundantNode相同，則將count加1
                count++;
            }

            next = next.next;
        }
        // 最後一個結點需要判斷出現的次數
        if (count == 1) {
            pre.next = new ListNode(lastNonRedundantNode.val);
        }

        return dummyNode.next;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.testCase6();
        System.out.println("原鏈表為");
        ListNode.print(head);

        System.out.println("刪除有序鏈表中重複的元素後的鏈表為");
        ListNode.print(deleteDuplicates(head));
    }
}

$1.01^{365} ≈ 37.7834343329$
$0.99^{365} ≈ 0.02551796445$
相信堅持的力量！