preface

“This is the seventh day of my participation in the August More Text Challenge. For details, see: August More Text Challenge.”

This time, I will summarize the problem of removing duplicate elements from linked lists

  1. NC25 Delete duplicate elements from ordered lists -I(simple)
  2. NC24 Delete duplicate elements from ordered lists -II(medium)

Delete the duplicated element -i from the ordered list

Description: Remove duplicate elements from a given list, so that all elements in the list appear only once. For example: if given list is 1→1→2, return 1→2. The list given is 1→1→2→3→3, and returns 31→2→3.

Thinking analysis: When next of the current node is not empty, determine whether val in cur is equal to val in cur.next. If it is equal, skip cur.next and let the next pointer in cur point to the next node in cur.next (equivalent to deleting cur.next). If it is not equal, update the cur.next

AC code:

    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head == null || head.next == null) return head;
        
        ListNode cur = head;
        
        while(cur.next ! =null) {if(cur.next.val == cur.val){
               cur.next = cur.next.next;
           }else{ cur = cur.next; }}return head;
    }
Copy the code

Remove duplicate element II from an ordered list

Description: Give a list in ascending order. remove all recurring elements from the list, leaving only elements that occur once in the original list. For example: given the list is 1→2→3→3→4→4→5, return 1→2→5. The list given is 1→1→1→2→3, and returns 2→3.

Thinking analysis: Different from the previous question, the repeated nodes need to be deleted, so add a virtual head node to avoid the special processing of deleting the head node. Start with cur pointing to the virtual head node, and then loop to determine whether the values of the next two adjacent nodes in cur are equal. In the case of equality, use the val variable to record the value of the current node that needs to be deleted, and then iterate backwards to delete the node whose value is val. In the case of inequality, it means that the node in cur

AC code:

    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head == null || head.next == null) {return head;
        }
        
        ListNode pre = new ListNode(-1);
        pre.next = head;
        
        ListNode cur = pre;
        
        while(cur.next ! =null&& cur.next.next ! =null) {if(cur.next.val == cur.next.next.val){
                int val = cur.next.val;
                
                while(cur.next ! =null&& cur.next.val == val){ cur.next = cur.next.next; }}else{ cur = cur.next; }}return pre.next;
    }
Copy the code