“This is the 9th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

preface

Delete duplicate element II from sorted list as follows:

There is a linked list in ascending order, and you are given the head node of the linked list. Please delete all the nodes in the linked list that have duplicate numbers, and only keep the original list that does not have duplicate numbers.

Returns a linked list of results, also in ascending order.

Example 1:

Input: head = [1,2,3,3,4,4,5]Copy the code

Example 2:

Input: head = [1,1,1,2,3]Copy the code

A, thinking

Delete the duplicate items in the linked list and keep the original list

Since it is stipulated in the title that the original linked list should be kept, it is not possible to create a new linked list to add unique nodes one by one.

It is easy to find duplicates in the linked list. There must be a pointer current to the current node and another pointer next to the next node. As long as the values of the two nodes are equal, it indicates that they are duplicated.

We found it impossible at this timecurrentPoints to the next element of the previous nodenext!

So we need a leading node before, which always points to the previous element of current, as shown in the diagram below

Graphical algorithm (adding front nodes)

Here is an example of strength in head = [1,2,3,3,4,4,5]

  1. Let’s add onebeforeNode, as shown in the figure below:

  1. becausecurrent 和 nextElement to point to1 和 2They are not equal, so they both point to the next element of themselves

  1. becausecurrent 和 nextElement to point to2 和 3They are not equal, so they go on to the next element of themselves

  1. At this timecurrent 和 nextThe elements that point to are equalnextYou have to go all the way downcurrentUnequal elements, as shown below:

  1. Delete duplicate elements

Next = next, current = next, next = next. Next, as shown in the figure below:

  1. The procedure for deleting subsequent duplicate elements is the same as above.

Second, the implementation

The implementation code

In the implementation code, current is replaced with before.next for brevity

    /** * Delete the duplicate item *@param head
     * @return* /
    public ListNode deleteDuplicates(ListNode head) {
        // Special circumstances
        if (head == null || head.next == null) {
            return head;
        }
        ListNode before = new ListNode(-1, head);   // The front node
        ListNode newHead = before;
        ListNode next = head.next;
        while(next ! =null) {
            if (next.val == newHead.next.val) {
                // As long as it is equal to the current value, it keeps going down
                while(next ! =null && next.val == newHead.next.val) {
                    next = next.next;
                }
                // Delete this node and the previous node
                newHead.next = next;
                if (next == null) { // If there are no more elements
                    break;
                }
                next = next.next;
            } else{ newHead = newHead.next; next = next.next; }}return before.next;
    }
Copy the code

The test code

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1.new ListNode(1.new ListNode(1.new ListNode(2.new ListNode(3)))));
        ListNode listNode2 = new ListNode(1.new ListNode(2.new ListNode(3.new ListNode(3.new ListNode(4.new ListNode(4.new ListNode(5)))))));
        ListNode listNode3 = new ListNode(1.new ListNode(1));
        new Number82().deleteDuplicates(listNode3);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section