鏈接列表：.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就沒有在名單上的影響，它只會修改變量的值。