“This is the 11th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

Deadbeat algorithm, at least one algorithm every day

Yesterday we talked about removing duplicate elements from sorted lists

Today let’s do an upgraded version of it

The title

This is problem 82 on Leetcode. Remove duplicate elements II from sorted lists

Given the head of a sorted list, delete all the nodes in the original list with duplicate numbers, leaving only the different numbers. Returns a sorted linked list.

Difficulty: Medium (suddenly medium)

Example 1:

Enter: head = [1.2.3.3.4.4.5] output: [1.2.5]
Copy the code

Train of thought

Step 1: Extract keywords from the topic

  • 1. Delete all duplicate digits from the original list, leaving only different digits.

This is upgrade ah, before at least we repeated the number still left a seedling, now fortunately, the only seedling is pulled out by others

Step 2: Analyze

  • 1. Consider what things don’t need to perform the first, if the head for [] or [1], then we will return directly, so the list items of the first few lines of code we can write, in fact, sometimes don’t have to write the code, because when cycle will judge, but we write also nothing wrong ah, we don’t need special pursuit of perfection, Write code that you can easily understand
if(! head||! head.next){return head;
}
Copy the code
  • 2. We need to consider what if the first node and the second node are duplicate nodes? So we declare a false node whose next points to head so that we can delete the first node
let dummy = new ListNode();
dummy.next = head;
// Virtual nodes must be declared. Virtual nodes are used to manipulate linked lists
let cur = dummy;
Copy the code

Now that the basic framework is in place, it’s time to fill in the framework

var deleteDuplicates = function(head) {
    if(! head||! head.next){return head;
    }
    let dummy = new ListNode();
    dummy.next = head;
    let cur = dummy;
    while(Judgment condition){if() {// The main code part
        }else{
            // Loop linked list must write codecur = cur.next; }}return dummy.next;
};
Copy the code

Why, some students will ask, does a cur point to dummy and not head? If you want to point to head, how do you change the next point, that is, how do you delete the first node

  • 3. So now we need to analyze the main logic, the main logic is clear to all of us, is to delete duplicate nodes, that must determine whether the value of the two nodes is the same ah, otherwise how to delete

Since our dummy has no value, the judgment condition should be written

if(cur.next.val === cur.next.next.val){
    
}
Copy the code

So we have the condition for the while, and then we record the equality, and then we delete the while loop

if(cur.next.val===cur.next.next.val){
            // Record the current equal value
            let value = cur.next.val;
            // Pay attention to the boundary problem
            while(cur.next&&cur.next.val===value){
                // Now we want to change the pointer, that is, to start deleting the valuecur.next = cur.next.next; }}Copy the code

So we have our answer

Answer key

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var deleteDuplicates = function(head) {
    if(! head||! head.next){return head;
    }
    let dummy = new ListNode();
    dummy.next = head;
    let cur = dummy;
    while(cur.next&&cur.next.next){
        if(cur.next.val===cur.next.next.val){
            // Record the current equal value
            let value = cur.next.val;
            while(cur.next&&cur.next.val===value){
                // Now we want to change the pointer, that is, to start deleting the valuecur.next = cur.next.next; }}else{
            // loop nodecur = cur.next; }}return dummy.next;
};
Copy the code

conclusion

When writing questions, we must consider several extreme test conditions, because the algorithm can not be recited, and consider several extreme conditions to let us write questions more correctly ✅

reference

Delete duplicate element II from sorted list