我只是在练习我的数据结构,并尝试制定一种从单链表中删除重复项的方法。这就是我所拥有的:
void removeDup() {
Node temp = head;
Node cur = null;
String s = "";
while(temp!=null) {
cur = temp;
if(!s.contains(temp.data + "")) {
s += temp.data + "";
}
else {
cur.next = temp.next;
}
temp = temp.next;
}
}
执行此方法后打印链表没有显示任何变化。我相信这是因为我没有正确地将前一个链接链接到当前链接的.next 值,但对我来说一切看起来都是正确的。我对其进行调试,似乎正确删除了该节点,但当我随后打印出链表时,重复的节点仍然出现。有建议吗?
最佳答案
代码复制自https://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/ :
方法1 - 暴力破解,找到所有的两个节点对,看看它们是否有相同的值,不确定调用System.gc()是否是一个好主意:
/* Function to remove duplicates from an
unsorted linked list */
void remove_duplicates() {
Node ptr1 = null, ptr2 = null, dup = null;
ptr1 = head;
/* Pick elements one by one */
while (ptr1 != null && ptr1.next != null) {
ptr2 = ptr1;
/* Compare the picked element with rest
of the elements */
while (ptr2.next != null) {
/* If duplicate then delete it */
if (ptr1.data == ptr2.next.data) {
/* sequence of steps is important here */
dup = ptr2.next;
ptr2.next = ptr2.next.next;
System.gc();
} else /* This is tricky */ {
ptr2 = ptr2.next;
}
}
ptr1 = ptr1.next;
}
}
方法2 - 使用hashset来帮助检测重复,我个人更喜欢这种方法:
/* Function to remove duplicates from a
unsorted linked list */
static void removeDuplicate(node head)
{
// Hash to store seen values, changed a little to compile for Java 8
HashSet<Integer> hs = new HashSet<Integer>();
/* Pick elements one by one */
node current = head;
node prev = null;
while (current != null)
{
int curval = current.val;
// If current value is seen before
if (hs.contains(curval)) {
prev.next = current.next;
} else {
hs.add(curval);
prev = current;
}
current = current.next;
}
}
关于java - 无法从链表中删除元素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52748889/