[数据结构与算法]Leetcode 82. Remove Duplicates from Sorted List II--删除链表中的重复节点，重复的节点均删除掉

Given the?head?of a sorted linked list,?delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return?the linked list?sorted?as well.

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

• The number of nodes in the list is in the range?[0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be?sorted?in ascending order.

package com.linkedlist;

/**
 * @Author you guess
 * @Date 2022/3/31 22:33
 * @Version 1.0
 * @Desc Leetcode[链表] 82. 删除排序链表中的重复元素 II
 * 删除重复节点（如果有2个节点值相同，把这2个节点均删掉；重复的节点均删除掉）
 */
public class Leetcode_82_RemoveDuplicatesfromSortedListII {


    public static void main(String[] args) {
        ListNode node72 = new ListNode(7, null);
        ListNode node7 = new ListNode(7, node72);
        ListNode node6 = new ListNode(6, node7);
        ListNode node5 = new ListNode(5, node6);
        ListNode node42 = new ListNode(4, node5);
        ListNode node41 = new ListNode(4, node42);
        ListNode node40 = new ListNode(4, node41);
        ListNode node3 = new ListNode(3, node40);
        ListNode node22 = new ListNode(2, node3);
        ListNode node21 = new ListNode(2, node22);
        ListNode node20 = new ListNode(2, node21);
        ListNode node11 = new ListNode(1, node20);
        ListNode node1 = new ListNode(1, node11);

        Leetcode_82_RemoveDuplicatesfromSortedListII main = new Leetcode_82_RemoveDuplicatesfromSortedListII();

        main.printListNode(main.deleteDuplicates(node1));
    }


    /**
     * Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Duplicates from Sorted List II.
     * Memory Usage: 41.7 MB, less than 93.02% of Java online submissions for Remove Duplicates from Sorted List II.
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode sentiel = new ListNode(0, head);
        ListNode pre = sentiel;
        while (head != null) {
            if (head.next != null && head.val == head.next.val) {
                while (head.next != null && head.val == head.next.val) {
                    head = head.next;
                }
                pre.next = head.next;
                head = head.next;
            } else {
                pre = pre.next;
                head = head.next;
            }
        }
        return sentiel.next;
    }


    /**
     * head每步都在往后移，pre.next指向遇到的第一个不同值（还需验证后续是否重复），pre指向不重复的值（已验证完后续无重复）
     * pre把不重复的值链接起来
     * sentinel指针一直没变，所以最后返回sentinel.next即可
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicatesSolution(ListNode head) {
        // sentinel
        ListNode sentinel = new ListNode(0, head);

        // predecessor = the last node
        // before the sublist of duplicates
        ListNode pre = sentinel;

        while (head != null) {
            // if it's a beginning of duplicates sublist
            // skip all duplicates
            System.out.println("外层while,head:" + head.val + ",head.next:" + head.next.val);
            if (head.next != null && head.val == head.next.val) {
                // move till the end of duplicates sublist
                while (head.next != null && head.val == head.next.val) {
                    head = head.next;
                    System.out.println("内层while,head:" + head.val);
                }
                // skip all duplicates
                pre.next = head.next;//只是指向后面第一个不同的值，并没有修改pre的指针。还需要继续判断后续是否重复

                // move forward
                head = head.next;
                System.out.println("pre:" + pre.val + ",head:" + head.val);
                // otherwise, move predecessor
            } else {
                pre = pre.next;//head与head.next值不同时才后移pre指针

                // move forward
                head = head.next;

                System.out.println("pre:" + pre.val + ",head:" + head.val);

            }
        }
        return sentinel.next;
    }


    /**
     * Deprecated
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates2(ListNode head) {
        ListNode pre = head;
        ListNode post = head.next;
        int postValue = post.val;
        while (post.next != null) {
            if (postValue == post.next.val) {
                post = post.next;
            } else {
                post = post.next;
                postValue = post.val;
                pre.next = post;
                pre = post;
//                post = post.next;
            }
        }
        return head;
    }


    public void printListNode(ListNode head) {
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }
    }

}

?