リンクリスト：.nextとtempリンクリストノードの定義

Question

LinkedListに関するインタビューの質問で問題を解決しています。

質問は一時バッファが許可されていない場合はどのようにこの問題を解決するだろうソートされていないリンクリスト FOLLOW UP から重複を削除するには...

コードを記述しているのですか？

私は解決策を読んでいましたが、解決策の3つの部分を理解していません。

まず、

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を使わなければならないのですか？ また、 テーブルソリューションにuniqueキーワードを入れた後、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; 
    } 
    [...] 
} 

[...] 
} 
} 

2番目の質問、第二の溶液から、それはプログラム重複キーワードを見つけるには、我々はそれを削除する必要があります。したがって、重複するキーワードを削除するために削除するtmpノードを宣言します。 しかし、私は本当に理由を理解していない"pre.next = tmpとcur = tmp"。 私はthet "cur = tmp"が現在のノードを次のノードに更新すると推測しています。しかし、私は理由について本当に確信していません。

第三に、ビッグoの部分のために。私は最初の解がO（n）であり、2番目の解がO（n^2）であると仮定しています。そうですか？

おかげ

Answer 1

最初の質問： Nは、ノードへの参照です。この関数でのみ有効なローカル参照です。

将来、リンクリストにアクセスしているとします。 ノードが検出される方法は、前のノードに位置する参照 'r'によって行われます。その参照を変更する必要があります。 nを変更すると、rには何の違いもありません。

C/C++の世界なら、nはノードへの一意のポインタのようなものだと考えてください。このポインタの値を変更すると 'r'の値が変更されますか？私はそうは思わない。

第2質問： ここでの疑問は、割り当てに関連する可能性があります。私たちは 'current.next'と言うと、オブジェクト 'current'の 'next'変数を参照しています。我々は、「次のノードに電流を進める」と言っているわけではない。そのため、 'current.next'は実際には変数を変更しません。私たちが 'current = current.next'と言うときは、「現在」が指しているノードを変更したいので、次のノードの「current.next」に変更したいと言っています。

でも、あなたは複雑さについて正しいと思います。

Answer 2

最初の質問：

n = n.next全く何のリスト自体には影響しません - それだけで、実際の要素に触れることなく、その次の要素に変数nの値を進めますリスト内のprev.next= n.nextを行う

は、prev参照するオブジェクトのフィールドnextを更新している - 、そこ[オブジェクトへの参照である] n.nextの値を置きます。

2番目の質問：

同じ問題、curr = tempは何のリストには影響を与えません、それだけで変数の値を変更します。