Leetcode 83. Remove duplicate elements from sorted linked lists

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

1. Title 📑

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

Example 1:

Enter: head = [1,1,2]

Output: [1, 2]

Example 2:

Enter: head = [1,1,2,3,3]

Output: [1, 2, 3]

Limitations:

  • 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

2. Ideas 🧠

Method 1: single pointer

  1. Sentence:
    • ifhead == nullIt returns null
    • ifhead.next == nullIf the next node is empty, the header is returned
  2. Initialization: definitionListNode cur Point to the head of the listhead
  3. Circular judgment:
    • whencur.next == nullIs the end of the cycle condition
    • whencur.val 和 cur.next.valIf it is equal, it means that the weight needs to be removedcurThe next pointer to the node whose value is the same can achieve the effect of de-duplication
    • whencur.val 和 cur.next.valNot equal, i.ecurMove to the next position to continue the loop

Method two: double pointer

In general, it is very convenient to insert and delete linked lists with double Pointers, but it is very tedious to insert and delete arrays in a certain location.

  1. Sentence:
    • ifhead == nullIt returns null
    • ifhead.next == nullIf the next node is empty, the header is returned
  2. Initialization: definitionListNode cur Point to the head of the listhead; defineListNode curNext Point to the head of the listhead
  3. Circular judgment:
    • The topics are already in ascending order, so the same data together pass throughcurNextTo find the next different number
    • cur.val 和 cur.next.valNot equal, that is, different numbers are found, thencur.next = curNextPoints the next node of the number at that position to that of the position already determinedcurNext, followed by cur = cur.nextContinue to move backward;
  4. Remember to point to the last nodenull, i.e.,cur.next = null.

Less nonsense ~~~~~ on the code!

3. Code: 👨💻

Commit AC for the first time

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }} * * /
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode cur = head;
        while(cur.next ! =null) {
            if(cur.val == cur.next.val){
                cur.next = cur.next.next;
            }else{ cur = cur.next; }}returnhead; }}Copy the code

Time complexity: O(N) N represents the length of the list

Space complexity: O(1)

Commit the SECOND TIME

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }} * * /
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode cur = head;
        ListNode curNext = cur.next;
        while(curNext ! =null) {
            if(cur.val ! = curNext.val) { cur.next = curNext; cur = cur.next; } curNext = curNext.next; } cur.next =null;
        returnhead; }}Copy the code

Time complexity: O(N) N represents the length of the list

Space complexity: O(1)

4, summarize

The biggest difficulty of this topic is whether to understand the structure of the linked list, understand the double pointer, for beginners double pointer is a very headache.

5. Related operations of linked lists

Link to 🔗

18. Remove list nodes – nuggets

Leetcode 21. Merge two ordered lists – nuggets

22. The k node from the bottom of the list – nuggets

Sword finger Offer 24. Reverse the list – nuggets

❤️ from the LeetCode Basic Algorithms column subscribe to ❤️

The original intention of the director to write blog is very simple, I hope everyone in the process of learning less detours, learn more things, to their own help to leave your praise 👍 or pay attention to ➕ are the biggest support for me, your attention and praise to the director every day more power.

If you don’t understand one part of the article, you can reply to me in the comment section. Let’s discuss, learn and progress together!

83. Delete duplicate elements from sorted lists