问题是从未排序的链表中删除重复项。使用哈希集可以跟踪该集中已有的值。
我不明白 if, else 块在做什么。 尤其是代码,prev = current。
这会覆盖之前的上一个吗?
我在白板上画了多个图表,无法理解这段代码的流程
public void removeDuplicateFromUnsortedList() {
HashSet<Integer> hs = new HashSet<Integer>();
Node current = head;
Node prev = null;
while(current != null) {
int current_data = current.data;
if(hs.contains(current_data)) {
prev.next = current.next;
}
else {
hs.add(current_data);
prev = current;
}
current = current.next;
}
}
这就是想要的结果,有效。
打印输出: 1 --> 1 --> 4 --> 2 --> 4 --> 2 --> 2 --> 空
打印输出: 1 --> 4 --> 2 --> 空
我会尽力为您找出答案! (我知道这已经 4 岁以上了,但无论如何)
基本上,如果 HashSet 不包含当前数据,那么我们不会将其从 LL 中删除,然后我们将 prev 设置为当前节点,并将 curr 设置为下一个节点。我们正在向前推进。
如果 HashSet 确实包含当前数据,我们将 curr 向前移动,但 prev 保持在原来的位置,并且 prev.next 设置为跳过当前节点以将其删除。
我们的LL:
"index": 0 (head) 1 2 3 4 5 6 7
data: 1 1 4 2 4 2 2 null
第一部分:
Node curr = head; // node at index 0
Node prev = null;
迭代
迭代 1:curr == head
"index": 0 (head) 1 2 3 4 5 6 7
data: 1 1 4 2 4 2 2 null
curr
curr_data = curr.data; // curr_data = 1
if (hs.contains(curr_data)) {/* hs is empty */}
else {
hs.add(curr_data);
prev = curr; // prev = head
}
curr = curr.next; // curr = node at index 1
// hs = {1}
迭代 2:curr == 索引 1 处的节点
"index": 0 (head) 1 2 3 4 5 6 7
data: 1 1 4 2 4 2 2 null
prev curr
curr_data = curr.data; // curr_data = 1
if (hs.contains(curr_data)) {. // hs = {1}
// now we set the previous node's .next to be the current node's .next,
// thus removing the current node from the LL
prev.next = curr.next;
}
curr = curr.next; // curr = node at index 2
// hs = {1}
在第二次迭代之后,curr的数据是重复的,前一个节点的.next更改为curr的.next,绕过curr并将其从列表中删除。在这种情况下,prev 不会更改,因为 curr 现在将是索引 2 处的节点,但索引 1 处的节点已被删除,因此 prev 保持在原来的位置。
迭代 3:curr == 索引 2 处的节点
"index": 0 (head) 1 2 3 4 5 6 7
data: 1 1 4 2 4 2 2 null
prev curr
curr_data = curr.data; // curr_data = 4
if (hs.contains(curr_data)) {/* hs = {1} */}
else {
hs.add(curr_data);
prev = curr; // prev = node at index 2
}
curr = curr.next; // curr = node at index 3
// hs = {1, 4}
迭代 4:curr == 索引 3 处的节点
"index": 0 (head) 1 2 3 4 5 6 7
data: 1 1 4 2 4 2 2 null
prev curr
curr_data = curr.data; // curr_data = 2
if (hs.contains(curr_data)) {/* hs = {1, 4} */}
else {
hs.add(curr_data);
prev = curr; // prev = node at index 3
}
curr = curr.next; // curr = node at index 4
// hs = {1, 4, 2}
迭代 5:curr == 索引 4 处的节点
"index": 0 (head) 1 2 3 4 5 6 7
data: 1 1 4 2 4 2 2 null
prev curr
curr_data = curr.data; // curr_data = 4
if (hs.contains(curr_data)) { // hs = {1, 4, 2}
// again, now we set the previous node's .next to be the current node's .next,
// thus removing the current node from the LL
prev.next = curr.next;
}
curr = curr.next; // curr = node at index 4
// hs = {1, 4, 2}
迭代 6:curr == 索引 5 处的节点
"index": 0 (head) 1 2 3 4 5 6 7
data: 1 1 4 2 4 2 2 null
(rem) prev (rem) curr
curr_data = curr.data; // curr_data = 2
if (hs.contains(curr_data)) { // hs = {1, 4, 2}
// again, now we set the previous node's .next to be the current node's .next,
// thus removing the current node from the LL
prev.next = curr.next;
}
curr = curr.next; // curr = node at index 6
// hs = {1, 4, 2}
迭代 7:curr == 索引 6 处的节点
"index": 0 (head) 1 2 3 4 5 6 7
data: 1 1 4 2 4 2 2 null
(rem) (rem) prev curr
curr_data = curr.data; // curr_data = 2
if (hs.contains(curr_data)) { // hs = {1, 4, 2}
// again, now we set the previous node's .next to be the current node's .next,
// thus removing the current node from the LL
prev.next = curr.next;
}
curr = curr.next; // curr = node at index 6
// hs = {1, 4, 2}