“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