<> Core test site ： Linked list operation , Critical condition check , Special case handling

In a sorted linked list , There are duplicate nodes , Please delete the duplicate nodes in the linked list , Duplicate nodes are not retained , Return chain header pointer .

Analysis I ：（ Not advocate ）
It is easy to solve this problem , And it is not easy to make mistakes when writing code as follows ：

* Traverse the linked list , Record node values of duplicate nodes .
* Traverse the linked list again , Delete duplicate nodes one by one .
Dynamic diagram demonstration ：

This method needs to traverse the linked list twice , And it needs to open up additional memory space to store the node values of duplicate nodes , Therefore, it is generally not advocated .
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x),
next(NULL) { } };*/ class Solution { public: ListNode* deleteDuplication(
// If the linked list is empty or there is only one node, no operation is required return pHead; ListNode* cur = pHead; unordered_set<int>
filter; //1, Traverse the linked list to find duplicate nodes , Store node values in filter while (cur->next) { if (cur->val == cur->
next->val) filter.insert(cur->val); cur = cur->next; } //2, Delete duplicate nodes one by one
pHead->next; } if(pHead == nullptr) return nullptr; // Then delete the remaining duplicate nodes ListNode* prev
= pHead; ListNode* last = prev->next; while(last) { if(filter.find(last->val) !=
filter.end()) { prev->next = last->next; last = last->next; } else { prev =
prev->next; last = last->next; } } return pHead; // Return chain header pointer } };
Analysis II ：（ Positive solution ）
Of course, we should try our best to solve this problem while traversing the linked list , At this time, we need to use two pointers to complete , The process involves a lot of detail , The general steps are as follows ：

*
For the convenience of subsequent operation , First create a header node for the linked list .

*
Use pointer prev and last Traversal linked list , Initial time prev Point to head node ,last Points to the next node of the head node .

*

When last When the node value pointed to is the same as the node value of the next node ,last Move back alone , until last The node value pointing to the node is different from the node value of the next node , Now let prev Pointing node last Last node of , Finally let last Point to the next node （ Not moved back in the figure ）.

*
When last The node value pointed to is different from the node value of the next node ,prev and last Move back together .

Go on like this , until last Traverse the linked list , The duplicate nodes in the linked list are all deleted , Finally, return the linked list pointed to by the head node .

Dynamic diagram demonstration ：

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x),
next(NULL) { } };*/ class Solution { public: ListNode* deleteDuplication(