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

preface

Delete duplicate elements from the sorted list as follows:

There is a linked list in ascending order. Given the head node of the linked list, remove all duplicate elements so that each element appears only once.

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

Example 1:

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

Example 2:

Head = [1,1,2,3,3]Copy the code

A, thinking

Delete all the duplicate elements in the list. Delete all the duplicate elements in the list only once.

Because we can compare the current element with the next element next to see if the next element is repeated, there is no need for a preceding element.

The general steps are as follows:

Current: indicates the current element. Next: indicates the next element of the current element

  1. currentPointing to the first element,nextPoint to the second element
  2. Start traversing the list whennextIs null, the traversal ends
  3. If it happens in the process of iterating againnextThe value of andcurrentIf the value of is the same, it indicates that a duplicate value occursnextKeep going down until you find thetacurrentDifferent elements.Then willcurrentThe next node points tonextAnd thencurrentMoves to the new head node, i.ecurrentPoint to thenextAnd thennextPoint to thenextThe next element of
  4. ifcurrent 和 nextIf the value of is not the same, they all refer to the next element of themselves
  5. Returns the original head nodeheadAs a result

For example

Here, head = [1,1,2,3,3] is used as an example

  1. Initialization:currentPoint to the first node,nextPoint to the second node
  2. I start walking, and then I havecurrent.val == next.val, so it moves downnextUntil thenextPoint to the2. thencurrent.next = next; current = next; next = next.next
  3. If I keep going,current 和 nextPoint to the2 和 3They’re not equal, so they’re moving down.current = current.next; next = next.next
  4. If I keep going,current 和 nextPoint to the3 和 3It’s equal, so it’s moving downnextUntil thenextI moved it off the list, sonext = null. At this time to updatecurrentCan,current.next = next; current = next
  5. Return to originalheadThe nodes, the linked list has become1 -> 2 -> 3

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public ListNode deleteDuplicates(ListNode head) {
        // Special case (only one element or no element)
        if (head == null || head.next == null)
            return head;
        ListNode current = head;
        ListNode next = head.next;
        while(next ! =null) {
            // If there are duplicate elements
            if (next.val == current.val) {
                while(next ! =null && next.val == current.val) {
                    next = next.next;
                }
                current.next = next;
                current = next;
                if (next == null) { // If there are no more elements, end the loop
                    break;
                }
                next = next.next;
            } else{ current = current.next; next = next.next; }}return head;
    }
Copy the code

The test code

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1.new ListNode(1.new ListNode(2.new ListNode(3.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 Number83().deleteDuplicates(listNode1);
    }
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