链表和指针澄清

Question

破解编码面试链表问题:编写代码从未排序的链表中删除重复项，解决方案是

public static void deleteDups (LinkedListNode n){
  Hashtable table = new Hashtable();
  LinkedListNode previous = null;
  while(n!=null){
      if(table.containsKey(n.data)){
          previous.next = n.next;
      } else {
          table.put(n.data, true);
          previous = n;
      }
      n = n.next;
  }
}

我的问题是为什么n = n.next不改变传递到函数的链表，但previous.next = n.next和previous = n确实改变传递进来的链表?

Answer 1

n是对LinkedListNode的引用。通过在那里设置不同的值，您不会修改原始LinkedListNode，只是将其引用更改为其他内容。换句话说，你"记住"了标签"n"下的新东西，但你没有修改原来的"n"。

X x = new X();
x = new X(); // this does not modify the original x

previous是LinkedListNode，通过设置该LinkedListNode的值，您正在修改它。

X x = new X();
x.y = new Y(); // this does mofiy the original x

换句话说，你是在为你记住的值"previous"设置一个属性。

而且，正如dimo414已经提到的，在这里使用HashTable是一个坏主意。使用一个简单的(Hash-)集合的理由就足够了。

Answer 2

n是指向相关链表节点的指针。

n = n.next

只是将指针移动到下一个节点。

previous.next = n.next

改变节点"previous"的位置。以前的。Next是对象"previous"中包含的值，即在previous之后的节点。所以之前。Next = n.next修改"previous"节点对象