无法从链表中删除元素？

Question

我只是在练习我的数据结构并尝试创建一种方法来从单个 linked 列表中删除重复项。这是我的：

        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;
            }
        }

执行此方法后打印 linked 列表显示没有任何变化。我相信这是因为我没有正确地将之前的 link link 转换为当前的 link's.next 值，但对我来说一切看起来都是正确的。我对其进行了调试，它似乎正确地删除了节点，但是当我随后打印出 linked 列表时，重复的节点仍然出现。建议？

Answer 1

代码复制自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; 
    } 
}

方法二——使用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; 
        } 

    }

Answer 2

首先，我认为您选择将之前的所有内容保存在一个字符串中可能是个坏主意。

例如，如果您为它提供一个包含 {x,y, xy} 的列表。第三项将被检测为重复项。结合简单的替代方法。
在某个集合中保留以前的值/为每个元素检查是否有其他等效项。对所有东西进行排序，然后检查人们的邻居。

你设置 cur = temp;在循环的顶部，这样做 cur.next = temp.next;之后什么都不做。不要在循环的顶部将 cur 设置为 temp 或仅在循环之后更改它。

Answer 3

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

无法从链表中删除元素？

Unable to delete an element from a linked list?

java

traversal

linked-list

data-structures

singly-linked-list