链接列表：.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;。但是，我们并不确定在代码中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和cur = tmp”的原因。 我猜测“cur = tmp”会将当前更新到下一个节点。不过，我并不确定其中的原因。

三，对于大部分。我假设第一个解决方案将是O（n），第二个解决方案将是O（n^2）。这样对吗 ？

感谢

Answer 1

第一个问题： Ñ是一个节点的引用。这是本地参考，仅在此函数中有效。

假设我们将来正在访问链表。 节点被发现的方式是通过位于前一个节点中的引用'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就没有在名单上的影响，它只会修改变量的值。