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

This article focuses on "how to remove duplicates from an unordered list". Interested friends may wish to take a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to remove duplicates from an unordered list.

Sequential deletion

The delete operation is performed directly on the linked list through a double loop. The outer loop uses a pointer to traverse the entire linked list from the first node, and then the inner loop traverses the rest of the nodes with another pointer, deleting the same nodes as the data domain of the node referred to by the pointer traversed by the outer loop, as shown in the following figure.

Suppose the outer loop starts traversing from outerCur, and when the inner loop pointer innerCur traverses to the position (outerCur.data==innerCur.data) shown in the solid line above, the node pointed to by innerCur needs to be deleted.

The specific steps are as follows:

Use tmp to record the address of the node to be deleted.

In order to be able to continue traversing the remaining nodes in the list after deleting the tmp node, make the innerCur pointer point to its successor node: innerCur=innerCur.next.

Removes the tmp node from the linked list.

The implementation code is as follows:

Running result:

Algorithm performance analysis

Because this method uses double loops to traverse the linked list, the time complexity is O (N ^ 2). Where N is the length of the linked list. In the process of traversing the linked list, constant additional pointer variables are used to store the current traversing nodes, precursor nodes and deleted nodes, so the space complexity is O (1).

Recursive method

The main idea is as follows: for node cur, the repeated nodes in the sub-linked list headed by cur.next are deleted recursively, and then the nodes with the same data domain as cur are found and deleted from the sub-linked list headed by cur.next.

The implementation code is as follows:

Algorithm performance analysis

This method is similar to method one, in essence, because this method requires double traversal of the linked list, the time complexity is O (N ^ 2). Where N is the length of the linked list. Because the recursive method adds many additional function calls, in theory, this method is less efficient than the previous method.

Space for time

In general, in order to reduce the time complexity, it is often achieved by using auxiliary space when the conditions permit.

Specifically, the main ideas are as follows.

Create a HashSet,HashSet whose content is the node content that has been traversed, and initialize it to empty.

Traversing all the nodes in the linked list from scratch, there are two possibilities:

If the node content is already in the HashSet, delete the node and continue traversing backwards.

If the node content is not in the HashSet, keep the node, add the node content to the HashSet, and continue traversing backwards.

"extension: how do I remove duplicates from an ordered linked list?"

Such as linked list: 1, 3, 5, 5, 7, 7, 8, 9

After weight removal: 1, 3, 5, 7, 8, 9

Analysis and solution

The method introduced above is also suitable for the case of ordered linked list, but because the above method does not make full use of the condition of ordered linked list, the performance of the algorithm is definitely not optimal. In this topic, because the linked list is ordered, there is no need to traverse the linked list twice. Therefore, there are the following ideas: use cur to point to the first node of the linked list, which needs to be discussed in the following two cases.

If cur.data==cur.next.data, delete the cur.next node.

If cur. data contains cur.next.data, then cur=cur.next, continue to traverse the rest of the nodes.

At this point, I believe you have a better understanding of "how to remove duplicates from an unordered linked list". You might as well do it in practice. 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.