インタビュー準備:単独にリストされたリスト－パート2

あなたが単独でリンクされたリストに慣れていないならば、このポストが我々がやめたところから続くので、パート1を読んでください.
最初の簡単なレビュー:
注:私は“リンクリスト”を参照するとき、私は単独リンクリストを参照しています.(二重にリンクされたリストもありますが、別の時間に保持します).
リンクリストは配列のようなものです.違いは、リンクリストが配列のようなインデックスを持っていないことです.リンクリストは開始点(通常「頭」)と終点(通常「尾」と呼ばれる)と呼ばれます.リストの指定された要素(“ノード”とも呼ばれる)にアクセスする場合は、常に頭の先頭にあるリンクリストを横断しなければなりません.
あなたは川の1つの銀行に立っていると想像してください.川に橋を架ける大きな岩がある.これで、川の片側から川の反対側に向かいます.ああ、その岩の橋は一方向です!
を、それはレビューだった.さて、リンクされたリストを含むインタビューで尋ねられるかもしれない一般的なアルゴリズムについて話しましょう.

リンクリストの中央値を見つける

我々は、上記のようにリンクリストを与えられている.私たちのリンクリストは5ノードがあります.その第1のノード(またはヘッド)は、整数「5」を含む.このノードは「4」を指す.“4”ポイントを“7”など.最後のノード「10」は「NULL」を指します.私たちの仕事は、ノードの中央値が何であるかを調べることです.
ブルートフォースの方法だけリストを横断し、カウンタを保つことができるので、我々はどのくらいのリストを見つけることができます.“NULL”を押すとリストの最後に到達したことを知っています.今、ちょうど2でカウンタを分割し、我々は10進数を取得する場合、結果をフロア.その後、“結果の”回数で2番目の時間を中央値を見つけることができます.
しかし、代わりにインタビュアーを感心させましょう.彼に本当に洗練されたやり方を見せましょう.我々は、ロバートW .フロイドに起因する“亀とウサギ”アプローチを使用します.リンクリストの先頭に亀とウサギを入れましょう.ウサギは、亀の2倍の速さでリストを横断することができます.言い換えれば、亀は常にウサギとして地面の半分をカバーすることができます.
それでは、両方のリンクリストを横断し始めましょう.もちろん、ウサギは最初に終了します.彼はリンクリストの尻尾で止まらなければならない.しかし、ウサギがリンクされたリストの終わりに到達したら、カメはウサギと同じくらい半分しか横断していないことを知っています.何?“半分ほど多くの”リンクの半分または中間点を意味する!
今、我々は中央値を見つけました、そして、我々はとても効率的にそれをしました.私たちのブルートフォース法で2回横断するすべてのカウントと余分な時間の代わりに、我々は一度だけ“ポインタ”(ウサギと亀)を使用してリストを横断しました.
絵を見てください.

Got it here
では、JavaScriptでコード化しましょう.
まず、一部のクラスから2つのクラスを再作成しましょう:まず、個々のノードを作成するためのノードクラスを作ります.

class Node {
 constructor(val) {
   this.val = val
   this.next = next
 }
}

class SinglyLinkedList {
 constructor() {
   this.length = 0
   this.head = null
   this.tail = null
 }
}

では、新しいFindMidleElementメソッドのシェルを作成しましょう.変数の“tortoise”と“hare”をリンクリストの先頭に設定します.

class Node {
 constructor(val) {
   this.val = val
   this.next = next
 }
}

class SinglyLinkedList {
  constructor() {
   this.length = 0
   this.head = null
   this.tail = null
  }
  findMiddleElement() {
   let tortoise = this.head
   let hare = this.head         
  }
}

まず最初にすべきことは、リストが本当に存在しているかどうかを調べることです(このエッジケースのテストは、あなたがインタビュアーを実際につま先にしていることを示します!)
これを行う一つの簡単な方法は、頭があるかどうかを確認するだけです.リストに頭がない場合、リストがなく、“未定義”を返すことができます.(この場合は何を返すかをインタビュアーに尋ねてください.

class Node {
 constructor(val) {
   this.val = val
   this.next = next
 }
}

class SinglyLinkedList {
 constructor() {
   this.length = 0
   this.head = null
   this.tail = null
 }
 findMiddleElement() {


   let tortoise = this.head
   let hare = this.head         
   if(!this.head) {
    return undefined
  }
}

次は私たちの論理の「肉」です.我々は亀とウサギのリンクリストに沿って移動を開始します.しかし、我々のリストがどれくらいあるかを知りません.
私たちの“while”ループは、ウサギがリストの最後に到達するまで実行させます.どのようにウサギは、彼の実行を完了して知っていますか?2つの可能性があります.
1)ノードの奇数があるなら、彼がリストの最後にいるでしょう、彼が最後のノードに着くとき、彼は次のノードが「NULL」であるとき、彼が最後のノードにいるということを知っています.例えば、7ノードのリストでは、ノード1を1から始め、2ノードを同時に移動させると、ノード1からノード3へノード5までノード7に行く.ノード7では、次のノードはNULLである.これは、“while”ループの状態が“Hare ' s next next”ノードが“NULL”ではないことを意味します

現在、ノード数が偶数かどうかを考慮する.例えば、8つのノードがあり、ノード1においてHAREが開始された場合、ノード1にノード1にノード5にノード7に行く.その後、ノード7で2ノードをジャンプすると、リストから降りて“NULL”ランドになる.それで、私たちは彼が「NULL」土地(Hare != Null)でない限り、彼が行くのを続けて欲しいです
今、私たちの“while”ループのシェルに入れましょう.つの条件を"&&"論理演算子で結合します.

class Node {
 constructor(val) {
   this.val = val
   this.next = next
 }
}

class SinglyLinkedList {
 constructor() {
   this.length = 0
   this.head = null
   this.tail = null
 }
  findMiddleElement() {
   let tortoise = this.head
   let hare = this.head    

   if(!this.head) {
    return undefined
   }

   while ( hare !== null && hare.next !== null) {
   }
  }
}

次の部分は簡単です.“while”ステートメントの本文では、我々の英雄を行かせたい!次のノードに移動する各ヒーローに指示するために、“dot next”(. next)を使用します.それはカメが行くことができることを意味します.しかし、ウサギは2倍速く行きます.このように:

class Node {
 constructor(val) {
   this.val = val
   this.next = next
 }
}

class SinglyLinkedList {
  constructor() {
   this.length = 0
   this.head = null
   this.tail = null
  }
  findMiddleElement() {
   let tortoise = this.head
   let hare = this.head 
   if(!this.head) {
    return undefined
  }

  while ( hare !== null && hare.next !== null) {
    tortoise = tortoise.next
    hare = hare.next.next
  }
 }
}

そして最後に、我々の賞を取得します.一旦ループがコースを走らせるならば、我々のカメは連結されたリストの終わりに座っています.最後のリターン文でカメのデータ値を得て、アルゴリズムを完成させましょう.

class Node {
 constructor(val) {
   this.val = val
   this.next = next
 }
}

class SinglyLinkedList {
 constructor() {
   this.length = 0
   this.head = null
   this.tail = null
 }
 findMiddleElement() {
   let tortoise = this.head
   let hare = this.head     
   if(!this.head) {
    return undefined
  }

   while ( hare !== null && hare.next !== null) {
    tortoise = tortoise.next
    hare = hare.next.next
   }

   return hare.val
 }

}

この亀とウサギのアプローチは、他の種類の問題にも役立ちます.あなたが戻ってリンクされているリストや、エンド、ミドルポイント、または何か他の何かと交差するしようとしているサイクルの任意の種類を見ているときはいつでもあなたの後ろのバーナーにこのアプローチをしてください.
幸せなインタビューと最高の願い!