关于java:牛客网高频算法题系列BM16删除有序链表中重复的元素II

48次阅读

共计 1669 个字符，预计需要花费 5 分钟才能阅读完成。

给出一个升序排序的链表，删除链表中的所有反复呈现的元素，只保留原链表中只呈现一次的元素。

原题目见：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));
    }
}