题解 | #牛群排列去重#java
牛群排列去重
https://www.nowcoder.com/practice/8cabda340ac6461984ef9a1ad66915e4
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;
}
Set<Integer> uniqueSet = new HashSet<>();
ListNode prev = null;
ListNode current = head;
while (current != null) {
if (!uniqueSet.contains(current.val)) {
uniqueSet.add(current.val);
prev = current;
} else {
prev.next = current.next;
}
current = current.next;
}
return head;
}
}
这个问题涵盖了链表操作和双指针法的基本知识点。
- 链表操作：链表是一种常见的数据结构，可以通过节点之间的指针链接起来。在处理链表问题时，我们通常使用指针来遍历、插入、删除节点等操作。
- 双指针法：双指针法是一种常用的解题技巧，特别适用于数组或链表中需要快速定位和处理两个位置的情况。其中，快慢指针是一种常见的双指针方法，用于解决一些特定的问题，比如链表中的环检测、链表中点、链表倒数第 k 个节点等。
代码解释：
- 首先判断链表是否为空或只有一个节点，如果是，则直接返回原链表。
- 创建一个虚拟节点
dummy，将其下一个节点指向链表的头节点head。 - 定义两个指针
prev和current，初始时都指向dummy节点。 - 循环遍历链表，当
current的值和下一个节点的值相同时，说明存在重复的编号。 - 使用内层循环将
current向后移动，直到找到一个与其值不同的节点。 - 将
prev的next指针指向current，即删除了重复的编号，然后将prev移动到current的位置。 - 继续遍历链表，直到遍历完整个链表。
- 返回处理后的链表。
