To the chase

Delete duplicate element II from sorted linked 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

Compared with deleting duplicate elements in the linked list above, completely deleting the elements that appear multiple times, including the first occurrence, will also be deleted, which is slightly more difficult, because we need to delete the first occurrence. You can refer to the above, do a delete, and then record the deleted elements, iterate again, and then delete the first occurrence of the same val value.

But this is not innovative and requires a second walk through the list. How do you iterate through the list only once, removing all repeated elements (including the first occurrence)?

If a linked list is in ascending order, the same elements in the list must be adjacent

Never type if you can use pictures. Here I try to use a GIF to express my thoughts:

General idea:

1. Define a head as firstPre node. Why define firstPre? Because the linked list is one-way.

2. Compare first (current node) and next (next node). Due to the incremental nature of the linked list, the same node must be adjacent, that is, first and next may be repeated, so compare first and next

3. If not, move firstPre to the right, which creates new first and next (first is firstPre. Next, next is first.next)

4. Always compare first and next. If they are the same, delete next (point first to next. Next), mark first, and continue the comparison. There are two possible questions :(1) why mark first? Because the first node is the same, it makes sense that the first node should also be deleted. Currently, only the next node is deleted. The reason why it is not deleted is that three identical nodes may be linked together. (2) Why doesn’t firstPre move right? Similarly, it is necessary to consider whether there will be three same nodes adjacent to each other, and right shift will lead to omissions.

5. If the same operation is performed, perform 4

6. If no, perform 3 and delete the marked node.

show my code:

/** * 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) { let temp = new  ListNode(0) temp.next = head let firstPre = temp let isDeleteFirst = false do { console.log(firstPre) const first = firstPre ? firstPre.next : P if (first === null) {break} const next = first.next if (next &&first.val === next.val) {// Delete next, Next = next. Next continue} else {if (isDeleteFirst) {firstpre.next = first.next isDeleteFirst = false } else { firstPre ? firstPre = firstPre.next : firstPre = head } } } while (firstPre) return temp.next };Copy the code