题解 | #牛群排列去重#

题目考察的知识点：链表、链表节点操作、基本算法思想（遍历和删除节点）。

题目解答方法的文字分析：这道题目给定了一个链表，表示农场里一群牛，每头牛都有一个独特的编号，编号由一个整数表示。链表已经按照非降序排列。由于一些事故，导致一头牛可能多次出现在链表中。我们需要在链表中删除所有重复的编号，只保留所有牛的不重复编号，并返回已排序的链表。

为了解决这个问题，我们可以使用遍历链表的方法来检查每个节点的值是否满足删除条件。首先，我们定义一个辅助节点dummy作为链表的头节点，并将其指向链表的头节点，以便处理头节点的情况。然后，我们定义两个指针prev和curr，prev指向当前节点的前一个节点，curr指向当前节点。

在遍历链表时，我们需要检查当前节点和下一个节点的值是否相等。如果相等，说明出现了重复编号的牛，我们需要找到重复编号的最后一个节点，并将prev.next指向该节点，从而删除重复节点。注意，我们只保留一个重复节点，其余重复节点都被删除。如果当前节点和下一个节点的值不相等，说明当前节点是不重复的，我们将prev移动到curr，将curr移动到下一个节点，继续遍历链表。

最后，我们返回dummy.next作为结果链表的头节点。

本题解析所用的编程语言：Java

完整且正确的编程代码如下：

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) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        while (curr != null && curr.next != null) {
            if (curr.val == curr.next.val) {
                int valToRemove = curr.val;
                while (curr.next != null && curr.next.val == valToRemove) {
                    prev.next = curr.next;
                    curr = curr.next;
                }
            } else {
                prev = curr;
                curr = curr.next;
            }
        }
        return dummy.next;
    }
}