Связанный список: определение узла .next и temp связанного списка

Question

Я решаю проблему в вопросе об опросе о LinkedList.

вопрос в ...

Пишите код для удаления дубликатов из несортированного списка ссылок.если временный буфер не разрешен?

Я читал решение, и я не понимаю три части в решении.

Первый,

public static void deletedup(LinkedListNode n) 
{
     Hashtable table = new Hashtable();
     LinkedListNode prev = null;
     while(n != null)
     {
         if(table.containsKey(n.data))
          prev.next = n.next; //<--
          else
          table.put(n.data, true);
          prev = n;//<--
      }
       n =  n.next;
}

Первый-1 вопрос,В решении, если таблица содержит дублированное ключевое слово.они должны перейти к следующему узлу.Я думал, что нам просто нужно, чтобы n = n.next.Тем не менее, решение было prev.next = n.next ;.Тем не менее, мы не совсем уверены, что предыдущая часть кода.Почему мы должны использовать пред?Более того, после помещения уникального ключевого слова в табличное решение присвойте n значение prev ( prev = n; ).Зачем нам это делать?

Второй,

public static void deletedup(LinkedListNode head)
{ 
LinkedListNode pre = head;
LinkedListNode cur = pre.next;
while(cur != null){ 
  LinkedListNode runner =head;
while(runner != current)
{
  if(runner.data == cur.data)
  { 
      LinkedListNode tmp = current.next;
      pre.next = tmp;//<---
      current = tmp;//<--
      break;
  }
  [...]
}

[...]
}
}

Второй вопрос, из второго решения, это программа поиска дублированных ключевых слов, мы должны ее удалить.Поэтому они объявляют узел tmp для удаления, чтобы удалить дублирующиеся ключевые строки.Тем не менее, я не совсем понимаю причину сделать "pre.next = tmp и cur = tmp". Я предполагаю, что "cur = tmp" обновит текущий до следующего узла.Однако я не совсем уверен в причинах ..

В-третьих, для большой части.Я предполагаю, что первое решение будет O (n), а второе решение будет O (n ^ 2).Это правильно?

спасибо

Answer 1

Первый вопрос: n является ссылкой на узел. Это локальная ссылка, которая действительна только в этой функции.

Скажем, мы получим доступ к связанному списку в будущем. Способ обнаружения узла - это ссылка 'r', расположенная в предыдущем узле. Нам нужно изменить эту ссылку. Если мы изменим n, это не будет иметь никакого значения для 'r'.

Если вы из мира C / C ++, думайте, что n - это уникальный указатель на узел. Изменит ли значение этого указателя значение 'r'? Думаю, нет.

Второй вопрос: Я думаю, что ваши сомнения здесь могут быть связаны с заданиями. Когда мы говорим «current.next», мы имеем в виду переменную «next» в объекте «current». Мы не говорим «продвигать ток к следующему узлу». Вот почему «current.next» не изменит никаких переменных. Когда мы говорим «current = current.next», мы говорим: «Хорошо, я хочу изменить узел, на который указывает« current », и я хочу изменить его на« current.next », следующий узел.

Также , я полагаю, вы правы насчет сложности.

Answer 2

первый вопрос:

n = n.next не оказывает никакого влияния на сам список - он только увеличивает значение переменной n доследующий элемент, не касаясь фактических элементов в списке.

Выполнение prev.next= n.next обновляет поле next в объекте, на который prev ссылается -, и помещает значение n.next [которое являетсяссылка на объект] там.

второй вопрос:

Та же проблема, curr = temp не повлияет на список, она только изменит значениепеременная.