Leetcode–Remove Duplicates from Sorted List

这是我参与8月更文挑战的第11天，活动详情查看：8月更文挑战

83、Remove Duplicates from Sorted List

题意：

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]
复制代码

Example 2:

 Input: head = [1,1,2,3,3]
 Output: [1,2,3]
复制代码

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.

解题：

实现方式有两种：一个是根据遍历到的节点创建新的节点，另一个是将原来的节点取出，更改其 next 指向即可

创建新对象方式比较简单，哲理不再赘述。

取出原来节点，更改其next指向的方式中需要注意一点：

取出的前部节点会指向后面的节点，如果head链表为[2,2]，预期输出为[2]，然而实际输出可能是[2,2]，需要再取出前部元素之后切换其后面的指向关系，画图说明

1、创建对象的方式

 /**
  * 删除已排序链表中重复的节点元素
  * <p>
  * 通过构造新对象的方式组建新的链表
  * </p>
  */
 public static ListNode removeDuplicatesNodeWithCreateObj(ListNode head) {
     // 头节点的判空处理
     if (head == null) {
         return head;
     }
 ​
     // 构建头节点
     ListNode resultNode = new ListNode(head.val);
     // 前部分尾巴节点、后部分头节点（有点游标节点的意思）
     ListNode frontTailNode = resultNode;
     ListNode rearHeadNode = head.next;
 ​
     while (rearHeadNode != null) {
         // 如果二者值不相等，创建对象追加到前节点尾部
         if (frontTailNode.val != rearHeadNode.val) {
             frontTailNode.next = new ListNode(rearHeadNode.val);
             frontTailNode = frontTailNode.next;
         }
 ​
         // 更替后部头节点
         rearHeadNode = rearHeadNode.next;
     }
 ​
     return resultNode;
 }
复制代码

2、更改取出节点的next指向问题

 /**
  * 删除已排序链表中重复的节点元素
  * <p>
  * 通过改变next引用的方式取出重复，这种方式相对节省内存
  * 其中更替完后续节点之后，切断前部分节点的后续指向容易忽略
  * </p>
  */
 public static ListNode removeDuplicatesNodeWithChangeNextQuote(ListNode head) {
     // 构造头节点做引子节点，前一部分游标节点
     // 不要怕创建过多的类型引用，这样能表达清楚引用关系
     ListNode resultNode = new ListNode(0, head);
     ListNode frontTailNode = head;
     ListNode rearHeadNode = head;
     ListNode currentNode;
 ​
     while (rearHeadNode != null) {
         currentNode = rearHeadNode;
         rearHeadNode = rearHeadNode.next;
 ​
         // 切断前半部分的后续指向，这一步必须在后半部分的节点更替完成之后切断，因为指向的是同一个对象
         frontTailNode.next = null;
 ​
         // 判断节点值是否相同，如果不走这一层，直接死掉了
         if (frontTailNode.val != currentNode.val) {
             // 更新前节点
             frontTailNode.next = currentNode;
             frontTailNode = currentNode;
         }
     }
 ​
     return resultNode.next;
 }
复制代码