链表:.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;
}

第一个问题。在解决方案中，if表包含重复的关键字。他们必须转移到下一个节点。我在想我们只需要n=n.next。然而，解决方案是执行prev.next=n.next；。然而，我们并不能真正确定代码中的prev。为什么我们必须使用prev？此外在表解决方案中放入唯一关键字后，将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;
  }
  [...]
}
[...]
}
}

第二个问题，从第二个解决方案中，it程序发现重复的关键字，我们必须将其删除。因此，他们声明tmp node要删除以删除重复的keyowrds。然而，我真的不明白为什么要执行"pre.next=tmp and cur=tmp"我猜thet"cur=tmp"会将当前节点更新到下一个节点。然而，我真的不确定原因。。

第三，大o部分。我假设第一个解是O（n），第二个解是0（n^2）。对吗？

感谢

Answer 1

第一个问题： n是对节点的引用。它是一个仅在此函数中有效的本地引用。

假设我们将来会访问链接列表。发现节点的方式是通过位于上一个节点中的引用"r"。我们需要改变这种提法。如果我们改变n，对'r'没有任何区别。

如果你来自C/C++世界，可以把n想象成一个指向节点的唯一指针。更改此指针的值会更改"r"的值吗？我想不是。

第二个问题：我认为你的怀疑可能与任务有关。当我们说"current.next"时，我们指的是对象"current"中的"next"变量。我们并不是说"将当前节点推进到下一个节点"。这就是为什么"current.next"不会真正改变任何变量的原因。当我们说"current=current.next"时，我们是在说，好吧，我想更改"current"所指向的节点，我想将其更改为"current.next"，即下一个节点。

还有，我相信你对复杂性的看法是正确的。

Answer 2

第一个问题：

n = n.next对列表本身没有任何影响-它只会将变量n的值提升到其下一个元素，而不会触及列表中的实际元素。

执行prev.next= n.next是更新prev引用的对象中的字段next，并将n.next[它是对对象的引用]的值放在那里。

第二个问题：

同样的问题，curr = temp不会对列表产生影响，它只会修改变量的值。