题解 | 牛群排列去重 | Java

考察链表遍历操作，使用Java语言

根据条件有以下的情况：

1. 特殊情况：只有一个节点或者没有节点
2. 一般的情况

对于特殊情况，23行标准写法

一般情况下，利用链表的遍历操作，设置左右指针，思路如下：

固定左指针，不断遍历右指针，在遍历的过程中根据左右指针值的相同与否从而进行对应的操作。

注意，因为是右指针在动，所以在while的条件中均需要加上right.next!=null来防止空指针异常

26-28 左右指针对应取值不同时进行左右指针的更新

29-42是当发生左右指针值重复时的操作，其中包含右指针一直遍历到新的值（31-33）

这其中也包含两种情况，一种是找到新的取值，那么就删除left到right之间重复的取值（35-37）

也有可能之间的值一直重复到最后，那么需要直接删除left后面的所有值（44)

提供一些自测的例子：

{2,2,2,5,5,5}

{2,2,2,2}

{2,2,2,3,3,4,5,5,6}

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head==null||head.next==null) return head; //特殊情况处理
        ListNode left = head, right = head.next;
        while(right.next!=null){ //让右指针不断向右遍历
            if(left.val!=right.val){
                left = right;
                right = right.next; //与41行重复 可以提出到42 表示右指针一直遍历这个动作
            }else{ //发生取值重复的情况
                // 让右指针一直向后遍历 直到找到新的值 
                while(left.val==right.val&&right.next!=null){
                    right = right.next;
                }
                //一直检查直到发现新的值的时候将中间的进行删除
                if(left.val!=right.val){
                    left.next = right;
                    left = right; 
                }else{ //右指针已经遍历到了最后一个节点 结束遍历操作
                    break;
                }
                right = right.next;
            }
        }
        if(left.val==right.val) left.next=null;
        return head;
    }
}