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”，即下一个节点。

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