Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

One, foreword

👨🎓 Author: Bug Bacteria

✏️ blog: CSDN, Nuggets, etc

💌 public account: Magic House of the Circle of the Apes

🚫 special statement: original is not easy, reprint please attach the original source link and this article statement, thank you for your cooperation.

🙏 Copyright notice: part of the text or pictures in the article may come from the Internet or Baidu Encyclopedia, if there is infringement, please contact bug bacteria processing.

Hello, little friends, I am bug bacteria 👀. Gold three silver four, brush the month again. So whether you’re looking for a career change or a career change, get your act together and do the right thing 👣. So, quickly follow the pace of bug bacteria roll up ⏰, become strong from this moment ➕🧈.

In the process of reviewing articles, if you think the articles are helpful to you at all, please don’t be too mean with your likes and bravely light up the articles 👍. Your likes (collect ⭐️+ pay attention to 👨 port + message board) are the best encouragement and support for bugs on my creation path. Time does not abandon 🏃🏻♀️, nuggets stop 💕, cheer up 🏻

Ii. Title Description:

** Given the head of a sorted list, remove all duplicate elements so that each element appears only once. Returns a sorted linked list.

See the following example for details:

Example 1:

Input: head = [1,2]Copy the code

Example 2:

Head = [1,1,2,3,3]Copy the code

** Hint: **

  • The number of nodes in the linked list is in the range[0, 300] 内
  • -100 <= Node.val <= 100
  • The subject data ensures that the linked list is sorted in ascending order

LeetCode ⭐⭐

Iii. Analysis of Ideas:

Finally is to meet a linked list problem, this problem is actually quite simple, a little understanding of the structure of the linked list of students, will not hesitate, because the given is a sorted list, repeated element position must be continuous, a direct traversal to determine whether the elements before and after the same snap naked write to submit. But, next I still have to talk about this problem to solve the idea and steps, certainly there will be not understand the students, students can also review it.

We define a pointer cur to the head of the list and start iterating through the list:

  • If cur and cur.next have the same element, that means the two elements are duplicated. To do so, remove cur.next from the list (you can think of it this way: move the next pointer to cur to the next pointer to cur and skip it).
  • Otherwise, there is no node in the current linked list that corresponds to cur, so point cur to cur.next and continue the loop.
  • When the list is complete, we return to the head of the list.

Iv. Algorithm implementation:

AC code

The specific algorithm code is as follows:

Class Solution {public ListNode deleteDuplicates(ListNode head) {// Point to a header. ListNode cur = head; // while (cur! = null && cur.next ! = null) {// Skip the next node of the current node if it is equal. if (cur.val == cur.next.val) { cur.next = cur.next.next; } else {// not equal to the next node cur = cur.next; }} // return the header directly to the solution. return head; }}Copy the code

V. Summary:

The screenshot of leetcode submission results is as follows:

Complexity analysis:

  • Time complexity: O(n). Where n is the length of the list.
  • Space complexity: O(1).

All in all, this de-linked list problem is relatively simple, except that when the last node is iterated, if the cur.next node is empty, if the element corresponding to cur.next is directly fetched, it will definitely report an error. So you need to add this null-detection logic to your loop. In fact, the idea of using the fast and slow pointer can also solve this problem, this is your own offline try, I will not give you a demonstration, still have to catch the project.

In addition, there are thousands of ways to solve the problem, you are welcome to have a rich imagination, if you have a better idea or idea to solve the problem, please let me know in the comment section, we can learn from each other, we can grow faster.

Well, that’s all for this episode and I’ll see you next time.

Six, the previous recommendation:

  • Leetcode -1. Sum of two numbers
  • Leetcode – 9. Palindrome
  • Leetcode -13. Roman numeral to integer
  • Leetcode -14. The longest public prefix
  • Leetcode -20. Valid parentheses
  • Leetcode -21. Merge two ordered lists
  • Leetcode -26. Remove duplicates from ordered arrays

Vii. End of article:

If you want to learn more, check out bug Bug’s LeetCode Problem of the Day column! With you brush together, each column is attached with a detailed solution, hand in hand with you to solve the problem.

One person may feel very tired and difficult to persist in brushing, but a group of people will think it is a meaningful thing to brush, urge and encourage each other, and become stronger together.

Finally send you two words, with you!

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

☘️ Be who you want to be, there is no time limit, you can start whenever you want,

🍀 You can change from now on, you can also stay the same, this thing, there are no rules to speak of, you can live the most wonderful yourself.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

​

💌 If this article is helpful to you, please leave a like! (# ^. ^ #);

💝 if you like the article shared by bug fungus, please give bug fungus a point of concern! The danjun ‘ᴗ, you guys will have a cameo appearance with you.

💗 if you have any questions about the article, please also leave a message at the end of the article or add a group [QQ communication group :708072830];

💞 In view of the limited personal experience, all views and technical research points, if you have any objection, please directly reply to participate in the discussion (do not post offensive comments, thank you);

💕 copyright notice: original is not easy, reprint please attach the original source link and this article statement, all rights reserved, piracy will investigate!! thank you