This article originated from personal public account: TechFlow, original is not easy, for attention


Delete Sorted lists. Remove Duplicates from Sorted List II.

The official difficulty of this question is Medium, with 1,636 upvotes and 107 downvotes, with a pass rate of 36.3%. According to our previous analysis, the difficulty of this question is moderate, and the quality is very high, and received a lot of praise. In fact, this algorithm itself is not difficult, but it is not easy to implement completely without bugs. Let’s take a look.

The question

Given an ordered list with duplicate elements, remove all duplicate elements from the list. Returns a linked list that contains no repeating elements.

Now, the important thing to notice here, is that what we’re doing here is not just getting rid of the weight, getting rid of the superfluous elements, but getting rid of all the duplicate elements. For example, if 2 appears twice in a linked list, it’s a duplicate element, what we’re going to do is not get rid of a 2 and keep only one, but get rid of all the 2’s, because 2 is a duplicate element.

Let’s take a look at an example:

Input: 1->2->3->3->4->4->5
Output: 1->2->5
Copy the code

3 and 4 in the original list are duplicate elements, so they are removed.

Input: 1->1->1->2->3
Output: 2->3
Copy the code

solution

The quality of this problem is very high, this problem is typical of naked solution, but many people just can’t write out the problem, very basic skills. If I were lucky enough to interview for college admissions, I would probably choose this question. There is no algorithm will not be a problem, can not write out the basic skills must be not solid enough.

The linked list is already ordered, so the same elements must be placed next to each other, and we just need to remove them. But it’s easy to say, not easy to implement in linked lists. There are two main difficulties. One is that many people are not familiar with the operation of adding and deleting nodes in linked lists, especially in languages like C++, which may be more difficult because Pointers are involved. Another difficulty lies in the problem idea. What we need to do is not to repeat, but to delete all the repeated elements.

It may seem like the same thing as losing weight, but if you really think about it that way and go about it, you’re almost certainly going to run into problems.

Because the list is one-way, let’s say your current pointer is cur, and if you find a duplicate element in cur, you need to delete the current node as well. As we all know, a one-way list cannot go back, and to delete a node, you must use a pointer to the previous node. In addition, we need to maintain multiple Pointers at the same time, which increases the coding difficulty of the code.

There are two approaches to this problem. The first is that instead of processing on the original list, we create a new list to return to. So instead of deleting elements, we insert them, and only insert them if there is no duplicate of the current element. A new linked list is returned.

This is of course possible, there is no problem, I do this problem for the first time is to take this measure. In contrast, this method is easier because we don’t need to judge too many Pointers and positions. I’ll post the code at the time:

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
          // If there are less than 2 elements, return directly
        if (head == nullptr || head->next == nullptr) return head;
 int cur = head->val;  / / initialization  bool flag = false;  ListNode* ct = new ListNode(0);  ListNode* pnt = ct;  head = head->next;  // Iterate over the elements  while (head) {  int hd = head->val;  // Determine whether the current element is equal to the previous element  if(hd ! = cur) { // There is no repetition of the previous element  if(! flag) { // Store the previous element in the linked list  pnt->next = new ListNode(cur);  // List move  pnt = pnt->next;  }else flag = false;  // Update the previous element  cur = hd;  }else flag = true;  head = head->next;  }  // Handle the last element separately  if(! flag) pnt->next =new ListNode(cur);  return ct->next;  } }; Copy the code

Although there is no restriction on the solution, nor is it required to work on the original list, this method of creating a new list is suspected of circumventing the problem. So we have a second solution, which is to confront the problem head-on. We maintain multiple Pointers to determine whether the next element at the current position constitutes a repetition. If duplicate, delete the duplicate part.

As we said earlier, it is difficult to delete the current element in a one-way list, so we determine whether the next element will constitute a repeat. If they are duplicated, it is much more feasible to delete them. One of the problems with this is that it’s possible that the first element of the list is duplicate, and there’s no way to find the element before the first element. The solution to this problem is to artificially create an element for it before the first element. So we can string the whole process together, the only difficulty is coding.

If we’re careful, we can write code:

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:  def deleteDuplicates(self, head: ListNode) -> ListNode:  Create a new element at the head of the list so that the first element is the next element in the header pointer  node = ListNode()  node.next = head  # PNT points to the newly created element  pnt = node   while pnt.next is not None:  # cur points to the next location of the current location  We need to determine if elements of cur are repeated  cur = pnt.next  if cur.next is None:  break   # PTR points to cur's next  ptr = cur.next  # If PTR and cur are equal, then there is duplication and we need to skip all equal elements  if ptr is not None and ptr.val == cur.val:  while ptr is not None and ptr.val == cur.val:  ptr = ptr.next  pnt.next = ptr  If not, move PNT  else:  pnt = pnt.next   # Because we started with an artificial helper element  Remove it when you return  return node.next Copy the code

conclusion

The algorithm is pretty simple, and I think most people can figure it out, but it’s not so easy to implement. There are a lot of tricks involved, like we think we’re creating a new header, like we’re deleting the current element instead of deleting the next element, and so on. These techniques are not much, but when used flexibly, they can greatly reduce the complexity of our coding, and because of this, this problem is of high quality and worth doing.

A lot of people hate lists, they think they’re hard to do, they’re easy to write wrong, but it’s actually a very important part of the basics. Many companies like to examine candidates’ basic skills, and improving this ability is very helpful for us to apply for or work.

This is the end of today’s article, if you like this article, please invite a wave of quality sanlian, give me a little support (follow, forward, like).

This article is formatted using MDNICE