This is the 11th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Remove Duplicates from the Sorted List

The question:

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example 1:

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

Example 2:

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

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

Problem solving:

There are two implementation methods: one is to create a new node according to the traversed node, and the other is to take out the original node and change its next point

The way to create new objects is relatively simple, and the philosophy will not be discussed again.

Take out the original node and change the way it points to next.

If the head linked list is [2,2], the expected output is [2], but the actual output may be [2,2]. After the front element is retrieved, the pointing relation of the back element needs to be switched, and the drawing is illustrated

1. How objects are created
 /** * Remove duplicate node elements from a sorted list * 
 * Build a new list by constructing new objects * 
 */
 public static ListNode removeDuplicatesNodeWithCreateObj(ListNode head) {
     // The header node is null
     if (head == null) {
         return head;
     }
 ​
     // Build the header node
     ListNode resultNode = new ListNode(head.val);
     // The first part of the tail node, the second part of the tail node
     ListNode frontTailNode = resultNode;
     ListNode rearHeadNode = head.next;
 ​
     while(rearHeadNode ! =null) {
         // If the values are not equal, create an object appended to the end of the front node
         if(frontTailNode.val ! = rearHeadNode.val) { frontTailNode.next =new ListNode(rearHeadNode.val);
             frontTailNode = frontTailNode.next;
         }
 ​
         // Replace the backend node
         rearHeadNode = rearHeadNode.next;
     }
 ​
     return resultNode;
 }
Copy the code
2, change the next point problem of the fetching node
 /** * Remove duplicate node elements from the sorted list * 
 * Remove duplicate node elements by changing the next reference, which is relatively memory saving * after replacing the subsequent nodes, it is easy to ignore the previous part of the node reference * 
 */
 public static ListNode removeDuplicatesNodeWithChangeNextQuote(ListNode head) {
     // Construct the head node as the lead node, the first part of the cursor node
     // Don't be afraid to create too many type references to make the references clear
     ListNode resultNode = new ListNode(0, head);
     ListNode frontTailNode = head;
     ListNode rearHeadNode = head;
     ListNode currentNode;
 ​
     while(rearHeadNode ! =null) {
         currentNode = rearHeadNode;
         rearHeadNode = rearHeadNode.next;
 ​
         // This step must be done after the replacement of the second half of the node, because it is pointing to the same object
         frontTailNode.next = null;
 ​
         // Check whether the values of the nodes are the same. If you do not go through this layer, you will die directly
         if(frontTailNode.val ! = currentNode.val) {// Update the previous nodefrontTailNode.next = currentNode; frontTailNode = currentNode; }}return resultNode.next;
 }
Copy the code