Не удается удалить элемент из связанного списка?

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

Прежде всего, я думаю, что ваш выбор хранения всех предыдущих вещей в одной строке, вероятно, является плохой идеей.

Например, если вы добавили в список {x, y, xy}.третий элемент будет обнаружен как дубликат.Пара простых альтернативных методов.
Храните предыдущие значения в некоторой коллекции / для каждого элемента, проверяйте, эквивалентно ли что-либо еще.разбери все, потом проверь народы соседей.

Вы устанавливаете cur = temp;в верхней части цикла, так что cur.next = temp.next;потом ничего не сделаю.Не устанавливайте cur равным temp в верхней части цикла и не меняйте его после.

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

Код скопирован с 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 - использование хэш-набора для обнаружения дубликатов, мне лично этот метод больше нравится:

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

    }