题解 | #删除链表中重复的结点#

个人直观版解题思路：

通过快慢指针剔除重复节点，考虑到第一个节点可能存在重复，故要新建立一个头节点指向结果。

重复的节点存在的情况有两种：

1. 偶数个重复（双指针跳跃剔除偶数个重复）
2. 奇数个重复（repeat变量记录奇数个重复的情况，再排除）

具体意思是：

• 情况1比如： 2->3->3->4， 3重复了两次（偶数个重复），当slow->3,fast->3时
  • 满足第一种情况，则slow=fast.next=4, fast=slow.next=null，便直接跳过两个重复节点
• 情况2比如： 2->3->3->3->4，3重复了三次（奇数个重复），必然会经过第一种情况。然后完成第一种情况后，快慢指针分别指向：slow->3,fast->4时，repeat=3，虽然slow.val!=fast.val，但仍然是重复的节点
  • 满足第二种情况，则slow=fast=4, fast=fast.next=null，第二次跳过奇数个重复节点

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) { // 只有0个或1个结点，则返回
            return pHead;
        }
      //新建头节点
        ListNode res = new ListNode(0);
      //快慢指针
        ListNode slow = pHead, fast = pHead.next;
      //结果
        ListNode pre = res;
      //记录重复的情况
        int repeat = 0;
        while(fast!=null){
          //第一种情况：偶数个重复
            if(slow.val==fast.val){
                repeat = slow.val;
                slow = fast.next;
              //为了防止空指针异常
                fast = slow==null? null:slow.next;
          //第二种情况：奇数个重复
            }else if(repeat==slow.val){
                slow = fast;
                fast = fast.next;
           //无重复情况
            }else{
                res.next = slow;
                fast = fast.next;
                slow = slow.next;
                res = res.next;
            }
        }
      //最后的情况还要处理
        if(slow!=null && repeat!=slow.val){
            res.next = slow;
        }else{
            res.next = null;
        }
        return pre.next==null? null: pre.next;
    }
}