BM16 delete duplicate elements in the ordered linked list -ii

1 Topic introduction

Solution 1 :

Establish the sentinel node and then traverse the linked list to connect the unique node to the sentinel node
Time complexity ：O(n), among n Is the number of nodes in the linked list , Only one traversal
Spatial complexity ：O(1), Only temporary pointers are opened up , Constant order space

public class Solution {
    
    /** * * @param head ListNode class  * @return ListNode class  */
    public ListNode deleteDuplicates (ListNode head) {
    
        // write code here
        if(head == null){
    
            return null;
        }
        // 1:  Define two pointers , An element that appears only once , One is used to connect the element 
        ListNode ret = new ListNode(1);
        ListNode tep = ret;
        ListNode cur = ret;
        cur.next = head;
        cur = cur.next;
        while(cur != null && cur.next != null){
    
            //  If not, it means cur It points to the only element 
            if(cur.val != cur.next.val){
    
                tep.next = cur;
                tep = tep.next;
                cur = cur.next;
            }else{
    
                //  If they are equal, go on until you find the unequal element positions 
                while(cur != null && cur.next != null && cur.val == cur.next.val){
    
                    cur = cur.next;
                }
                //  take cur Pointer to the next element , if cur If it is empty, the following elements are all found , At this time, you need to manually connect the null pointer , Otherwise, it will jump out of the loop 
                cur = cur.next;
                if(cur == null){
    
                    tep.next = null;
                }
            }
        }
        //  If traversal is completed cur In the last element , Then you need to manually connect the last element , Because it's in ascending order , It means that the last element must be unique 
        if(cur != null && cur.next == null){
    
            tep.next = cur;
        }
        return ret.next;
    }
}

Solution 2 :

Use the idea of recursion to solve
Time complexity ：O(n)
Spatial complexity ：O(1)

public class Solution {
    
    /** * * @param head ListNode class  * @return ListNode class  */
    public ListNode deleteDuplicates(ListNode head) {
    
        if(head == null){
    
            return null;
        }
        if(head.next != null && head.val == head.next.val){
    // Duplicate values found 
                while(head.next != null && head.val == head.next.val){
    
                    head = head.next;// Delete 
            }
            return deleteDuplicates(head.next);// Delete the same node as the deleted node 
        }
        head.next = deleteDuplicates(head.next);// When no duplicate values are found , Just keep doing recursive operations 
        return head;
    }
}

Solution 3 :

utilize hashmap Do two iterations , Record the number of occurrences of each number for the first time , The second time, create a new sentinel node to connect the unique node .
Time complexity ：O(n)
Spatial complexity ：O(n)
This method is applicable to the case that the order of the linked list is random

public class Solution {
    
    public ListNode deleteDuplicates (ListNode head) {
    
        // Empty list 
        if(head == null) 
            return null;
        HashMap<Integer,Integer> mp = new HashMap<>();
        ListNode cur = head;
        // Traverse the linked list and count the number of occurrences of each node value 
        while(cur != null){
     
            if(mp.containsKey(cur.val))
                mp.put(cur.val, (int)mp.get(cur.val) + 1);
            else
                mp.put(cur.val,1);
            cur = cur.next;
        }
        ListNode res = new ListNode(0);
        // Add a header before the linked list 
        res.next = head; 
        cur = res;
        // Traverse the list again 
        while(cur.next != null){
    
            // If the node value count is not 1 
            if(mp.get(cur.next.val) != 1) 
                // Delete this node 
                cur.next = cur.next.next; 
            else
                cur = cur.next; 
        }
        // Remove the meter head 
        return res.next; 
    }
}