Удаление дупс из несортированного алгоритма LinkedList не имеет смысла - PullRequest
Новая
       75

Удаление дупс из несортированного алгоритма LinkedList не имеет смысла

0 голосов
/ 17 апреля 2020

Мне трудно понять следующий алгоритм. Здесь цель состоит в том, чтобы удалить дубликаты из несортированного LinkedList:

У нас есть класс Node: 

public class Node {
int data;
Node next;

Node(int data) {
    this.data = data;
}
}

Это метод удаления дубликатов из connectedList: 

private static void removeDuplicates(Node head) {

    if (head == null) {
        return;
    }

    Node current = head;
    while (current != null) {
        Node runner = current;
        while (runner.next != null) {
            if (runner.next.data == current.data) {
                runner.next = runner.next.next; // (1) <-- here
            } else {
                runner = runner.next;
            }
        }
        current = current.next;
    }
}

// Контрольный пример
Узел узел1 = новый узел (2);
Узел узел2 = новый узел (2); <- игнорируемый узел <br>Узел узел3 = новый узел (3);
Узел узел4 = новый узел (4);
Узел узел5 = новый узел (8);
Узел узел6 = новый узел ( 16);
Узел узел7 = новый узел (32);
Узел узел8 = новый узел (8);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node7;
node7.next = node8;
node8.next = null;

После выполнения (1) в первой итерации:
runner.data = 2
runner.next.data = 3
current.data = 2
current.next.data = 3 ??? ПОЧЕМУ?

ПРОБЛЕМА: Имеет смысл, что node 'runner.next.data' равен 3 , потому что теперь 2-й узел значения 2 игнорируется.
Но почему узел 'current' также игнорирует 2-й узел? Мы никогда не писали на узел 'текущий'. Мы взаимодействовали только с «бегущим» узлом .

...