©2020-2024 ioDraw All rights reserved
<> 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(
ListNode* pHead) { if(pHead == nullptr||pHead->next == nullptr)
// 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
// Delete the duplicate node of the header first while(pHead&&filter.find(pHead->val) != filter.end()) { pHead =
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(
ListNode* pHead) { if (pHead == nullptr || pHead->next == nullptr)
// If the linked list is empty or there is only one node, no operation is required return pHead; ListNode* head = new ListNode(0);
// Create header node （ Easy to operate ） head->next = pHead; // The head node establishes a relationship with the original linked list ListNode* prev = head; ListNode*
last= prev->next; while (last) { // No duplicate nodes were found ,prev and last Move back together while (last->next&&
last->val != last->next->val) { prev = prev->next; last = last->next; }
// Duplicate nodes found ,last Move back alone while (last->next&&last->val == last->next->val) { last =
last->next; } // There are three ways to get here ： //1, There are no duplicate nodes to delete , Because last->next == nullptr Here we are
//2, There are duplicate nodes to delete , Because last->next == nullptr Here we are （ The second half of the linked list needs to be deleted ）
//3, There are duplicate nodes to delete , Because last->val != last->next->val Here we are （ A section in the middle of the linked list needs to be deleted ） if (prev->next !=
last) // This indicates that there are duplicate nodes that need to be deleted { prev->next = last->next; } last = last->next; } return
head->next; // Return chain header pointer } };
Technology