Topic Description 1

Remove duplicate elements from sorted lists: there is a list in ascending order. You are given the head node of the list. Remove all duplicate elements so that each element appears only once.

Returns a linked list of results, also in ascending order.

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

Their thinking

  1. To delete duplicate elements, we definitely need a comparison, so we need two Pointers pre=head,cur=head.next
  2. We do not use virtual header, so that the head node is not deleted, if you encounter repeated deletion can be
  3. If there is a duplicate, the cur pointer continues backward until it reaches a node that is not equal to pre-. val
  4. If pre and cur do not overlap, connect the node pointed by pre to the node pointed by cur, i.e., pre. Next =cur

To the problem solving

var deleteDuplicates = function(head) { if(! head) return null; let pre = head, cur = head.next; while(cur) { if(pre.val === cur.val) { cur = cur.next; if(! Cur) {// If the last elements are repeated,pre points to null cur. Next = cur; } }else { pre.next = cur; pre = cur; // After comparing the first two non-repeating elements, pre and cur move back 1 bit each to compare the next two nodes cur = cur.next; } } return head; };Copy the code

2.

Delete duplicate elements from sorted list 2: there is a list in ascending order, give you the head node of this list, please delete all duplicate digits in the list, only the original list does not duplicate digits.

Returns a linked list of results, also in ascending order.

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

Extended thinking

  1. Instead of deleting a single duplicate element, this topic is to delete all duplicate elements
  2. Virtual headers are used because header nodes can be deleted repeatedly
  3. We use two Pointers again, but we use them differently: dummy pointer pre and comparison pointer cur
  4. Each time you compare cur and cur.next, both will be deleted if you repeat them, so keep pre before cur. If you compare different nodes, pre points to cur, cur=cur.next, so pre becomes the first node of the next group of comparisons
  5. Cur = null, pre. Next = null

To the problem solving

var deleteDuplicates = function(head) { if(! head) return null; let ret = new ListNode(-1,head),pre=ret, cur = head; while(cur && cur.next) { if(cur.val ! == cur.next.val) { pre = cur; Cur = cur.next; }else {while(cur && cur.next && cur.val === cur.next. Val) {cur = cur.next; } // Find the non-repeating node cur.next pre-next = cur.next; // The pre is connected to the non-repeating node, where the pointer does not need to be moved, because the non-repeating node is the starting point for the comparison of the next group of nodes cur = cur.next; if(! cur) { pre.next = cur; } } } return ret.next; };Copy the code