牛客网高频算法题系列-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$
置信保持的力量！