Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to delete duplicate nodes in the linked list by Java". Friends who are interested may wish to take a look. The method introduced in this paper is simple, fast and practical. Now let the editor to take you to learn "Java how to delete duplicate nodes in the linked list"!

Core test points: linked list operation, critical condition check, special case handling

There are duplicate nodes in a sorted linked list, please delete the duplicate nodes in the linked list, do not retain the duplicate nodes, and return to the chain header pointer.

Analysis 1: (not advocated)

The ways to solve this problem are simple and not easy to make mistakes when writing code:

Traverse the linked list and record the node values of the repeating nodes.

Go through the linked list again and delete the duplicate nodes one by one.

This method needs to traverse the linked list twice, and needs to open up additional memory space to store the node values of repeated nodes, so it is generally not recommended.

/ * 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) / / the linked list is empty or there is only one node without operation return pHead; ListNode* cur = pHead; unordered_set filter / 1. Traverse the linked list to find the duplicate nodes, and store the node values in filter while (cur- > next) {if (cur- > val = = cur- > next- > val) filter.insert (cur- > val); cur = cur- > next } / / 2. Delete the duplicate nodes one by one / / delete the repeating nodes of the header while (pHead&&filter.find (pHead- > val)! = filter.end ()) {pHead = pHead- > next;} if (pHead = = nullptr) return nullptr / / 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}}; Analytical 2: (positive solution)

Of course, we should solve this problem by traversing the linked list as much as possible, when we need to use two pointers together, which contains a lot of details, and the general steps are as follows:

1. For the convenience of subsequent operation, first create a header node for the linked list.

two。 Use the pointers prev and last to traverse the linked list, initially prev pointing to the header node and last pointing to the next node of the header node.

3. When the value of the node pointed to by last is the same as that of the next node, last moves backward alone until the value of the node pointed to by last is different from that of the next node. At this time, let the node pointed by prev point to the last node of last, and finally let last point to the next node (not moved back in the figure).

4. When the value of the node pointed to by last is different from that of the next node, prev and last move backward together.

Go on like this, until last traverses the linked list, all the duplicate nodes in the linked list are deleted, and finally return to the linked list pointed to by the header node.

/ * 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) / / the linked list is empty or there is only one node without operation return pHead ListNode* head = new ListNode (0); / / create header node (easy to operate) head- > next = pHead; / / establish relationship between header node and original linked list ListNode* prev = head; ListNode* last = prev- > next No duplicate nodes were found in while (last) {/ /. Prev and last moved back while (last- > next&&last- > val! = last- > next- > val) {prev = prev- > next Last = last- > next;} / / found duplicate nodes, last alone moved back while (last- > next&&last- > val = = last- > next- > val) {last = last- > next } / / there are three cases of arriving here: / / 1. There are no duplicate nodes that need to be deleted, because last- > next = = nullptr to this / / 2, there are duplicate nodes that need to be deleted Because last- > next = = nullptr to this point (the second half of the linked list needs to be deleted) / / 3, there are duplicate nodes that need to be deleted Because last- > val! = last- > next- > val (a segment in the middle of the linked list needs to be deleted) if (prev- > next! = last) / / indicates that there are duplicate nodes {prev- > next = last- > next that need to be deleted. } last = last- > next;} return head- > next; / / return chain header pointer}}; at this point, I believe you have a better understanding of "how to delete duplicate nodes in the linked list by Java", so you might as well do it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.