java - 链表 : definition of . 下一个和临时链表节点

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

第一个问题。在解决方案中，如果表包含重复的关键字。他们已经移动到下一个节点。我在想我们只需要 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;
  }
  [...]
}

[...]
}
}

第二个问题，从第二个解决方案中，它程序找到了重复的关键字，我们必须将其删除。因此，他们声明要删除的 tmp 节点以删除重复的关键字。但是，我不太明白这样做的原因“pre.next = tmp and cur = tmp”。我猜测“cur = tmp”会将当前节点更新到下一个节点。但是，我不太确定原因..

第三，对于大的部分。我假设第一个解决方案将是 O(n)，第二个解决方案将是 O(n^2)。对吗？

谢谢

Answer 1

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

假设我们将来要访问链表。发现节点的方式是通过位于前一个节点的引用“r”。我们需要更改该引用。如果我们改变 n，它不会对 'r' 产生任何影响。

如果您来自 C/C++ 世界，请将 n 视为指向节点的唯一指针。改变这个指针的值会改变‘r’的值吗？我想不是。

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

另外，我相信您对复杂性的看法是正确的。