“This is the 20th day of my participation in the December Gwen Challenge. Check out the event details: 2021 Last Gwen Challenge”

Delete duplicate element II from sorted list

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

Tip:

  • The number of nodes in the linked list is in the range[0, 300] 内
  • -100 <= Node.val <= 100
  • The subject data ensures that the linked list is sorted in ascending order

A traversal

Train of thought

Delete duplicate node II: As long as it is a duplicate element, it will be deleted directly, and no one will be retained. In other words, only the element that has only appeared once will be retained. The current node curr is equal to newHead

  • We declare a new header, newHead, to join the linked list and make it easier to handle boundaries

Since there are at least two nodes, so the last two nodes of the current node, if they exist, are directly determined to be equal.

  • If the value is equal, it is proved that the node belongs to repeatVal, and the value of the node is recorded by the variable repeatVal, and then curr.next is continuously updated as its next value curr.next-next, until the value of curr.next is not equal to repeatVal, so far, the repeated elements have been deleted

  • If not, we prove that curr. Next is an element that does not repeat itself only once, and the pointer to curr moves backwards, curr = curr.next

After the final processing is completed, return to Newhead.next

var deleteDuplicates = function (head) {
    if(! head)return head
    var newHead = new ListNode('head',head)
    var curr = newHead
    while(curr.next&&curr.next.next){
        if(curr.next.val===curr.next.next.val){
            var repeatVal = curr.next.val
            while(curr.next&&curr.next.val===repeatVal){
                curr.next = curr.next.next
            }
        }else{
            curr = curr.next
        }
    }
    return newHead.next
};
Copy the code