无法从链表中删除元素？

Question

我只是在练习我的数据结构并尝试制作一种方法来从单向链表中删除重复项。这就是我所拥有的：

        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 值，但在我看来一切都是正确的。我调试它，它似乎正确删除了节点，但是当我之后打印出链表时仍然出现重复的节点。建议？

Answer 1

代码是从https://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list/复制的：方法 1 - 蛮力，找到所有成对的两个节点，看看它们是否具有相同的值，不确定调用 System.gc() 是否是一个好主意：/* Function to remove duplicates from an&nbsp;&nbsp; &nbsp;unsorted linked list */void remove_duplicates() {&nbsp;&nbsp; &nbsp; Node ptr1 = null, ptr2 = null, dup = null;&nbsp;&nbsp; &nbsp; ptr1 = head;&nbsp;&nbsp; &nbsp; /* Pick elements one by one */&nbsp; &nbsp; while (ptr1 != null && ptr1.next != null) {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; ptr2 = ptr1;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; /* Compare the picked element with rest&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; of the elements */&nbsp; &nbsp; &nbsp; &nbsp; while (ptr2.next != null) {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /* If duplicate then delete it */&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (ptr1.data == ptr2.next.data) {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; /* sequence of steps is important here */&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dup = ptr2.next;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ptr2.next = ptr2.next.next;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.gc();&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else /* This is tricky */ {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ptr2 = ptr2.next;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; ptr1 = ptr1.next;&nbsp;&nbsp; &nbsp; }&nbsp;}方法二——使用hashset帮助检测重复，我个人更喜欢这个方法：&nbsp;/* Function to remove duplicates from a&nbsp;&nbsp; &nbsp; &nbsp; &nbsp;unsorted linked list */&nbsp; &nbsp; static void removeDuplicate(node head)&nbsp;&nbsp;&nbsp; &nbsp; {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; // Hash to store seen values, changed a little to compile for Java 8&nbsp; &nbsp; &nbsp; &nbsp; HashSet<Integer> hs = new HashSet<Integer>();&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; /* Pick elements one by one */&nbsp; &nbsp; &nbsp; &nbsp; node current = head;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; node prev = null;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; while (current != null)&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int curval = current.val;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// If current value is seen before&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (hs.contains(curval)) {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; prev.next = current.next;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; hs.add(curval);&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; prev = current;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current = current.next;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp;&nbsp; &nbsp; }&nbsp;

Answer 2

cur.next = temp.next不会改变任何东西。使用例如 Java 8：new LinkedList<>(Arrays.asList(1,2,1,3)).stream().distinct().collect(Collectors.toList());或者new LinkedHashSet<>(new LinkedList<>(Arrays.asList(1,2,1,3)))另见https://www.geeksforgeeks.org/remove-duplicates-from-an-unsorted-linked-list

Answer 3

首先，我认为您选择将所有以前的东西保存在一个字符串中可能是一个坏主意。例如，如果你给它提供了一个带有 {x,y, xy} 的列表。第三个项目将被检测为重复。几个简单的替代方法。将以前的值保存在某个集合中/为每个元素检查是否有其他等效项。排序一切，然后检查人们的邻居。你设置 cur = temp;&nbsp;在循环的顶部，因此执行 cur.next = temp.next;&nbsp;之后什么也不做。不要在循环的顶部设置 cur 等于 temp 或者只是在之后更改它。