Java 题解 | #牛群排列去重#

该题考察了链表去重和链表删除等链表相关基础操作。

首先需要理解题目要求，即删除链表中重复出现的节点。通过遍历链表，检查当前节点和下一个节点的值是否相等。如果不相等，将指针向后移动；如果相等，则需要进一步找到连续重复节点的末尾，并将前一个节点的next指针指向末尾节点的下一个节点，从而删除重复节点。

1. 首先判断特殊情况，如果链表为空或者只有一个节点，则直接返回链表头节点 head。
2. 创建一个虚拟头节点 dummy，将其指向链表头节点 head。
3. 初始化两个指针 pre 和 cur，分别指向虚拟头节点和链表头节点。
4. 进行循环，直到当前节点或者下一个节点为空：如果当前节点的值与下一个节点的值不相等，则将 pre 和 cur 指针都向后移动一位。如果当前节点的值与下一个节点的值相等，则进入内层循环，将 cur 不断向后移动，直到遇到一个和当前节点值不相等的节点为止。此时，cur 指向的是重复节点序列的最后一个节点。将 pre.next 指向 cur，相当于跳过了重复节点序列。
5. 返回虚拟头节点的下一个节点，即为去除重复节点后的链表头节点。

该算法通过遍历链表的方式，找到重复节点的序列，并直接跳过这些重复节点，从而实现删除链表中重复节点的功能。

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 dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;

        while (cur != null && cur.next != null) { 
            if (cur.val != cur.next.val) {
                pre = pre.next;
                cur = cur.next;
            } else {
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                pre.next = cur;
            }
        }

        return dummy.next;
    }
}