면접준비: 단사슬표-2부분

면접 준비를 계속합니다. 만약 당신이 단쇄표에 익숙하지 않다면, 첫 번째 부분을 읽어 주십시오. 왜냐하면 이 문장은 우리가 떠난 곳에서 계속될 것입니다.
먼저 빠르게 살펴보겠습니다.
주: 내가 체인 시계를 언급했을 때, 나는 단일 체인 시계를 가리킨다.(이중 링크 목록도 있지만 우리는 한동안 보류할 것이다)
체인 테이블은 그룹과 유사합니다. 이 테이블은'유사 목록'의 대상입니다.다른 점은 체인 테이블에 수조와 같은 색인이 없다는 것이다.체인 테이블은 시작점이 있습니다 (일반적으로 머리와 끝점이라고 함).목록에 있는 주어진 요소 ('노드'라고도 함) 에 접근하려면 체인 테이블을 훑어보고 머리부터 시작해야 합니다.
상상해 봐, 네가 강 기슭에 서서 그것을 건너고 싶어.일련의 큰 암석이 강 위에 다리를 형성했다.이제 강의 한쪽 (머리) 에서 강의 다른 쪽 (끝) 으로 건너갈 수 있습니다.오, 그래, 그 돌다리는 단방향이야!
네, 이것이 바로 평론입니다.이제 체인 테이블과 관련된 인터뷰에서 물어볼 수 있는 일반적인 알고리즘에 대해 이야기해 보겠습니다.

체인 테이블의 중간 값 찾기

우리는 위의 그림과 같이 링크 목록을 얻었다.우리의 체인 시계는 다섯 개의 노드가 있다.첫 번째 노드나 헤더에는 정수'5'가 포함되어 있습니다.이 노드는 "4"를 가리킨다.'4'는'7'을 가리킨다.마지막 노드'10'은'null'을 가리킨다.우리의 임무는 노드의 중점이 무엇인지 찾아내는 것이다.
만력 방법은 목록을 훑어보고 계수기를 보존하는 것일 수도 있다. 그러면 목록이 얼마나 길었는지 알 수 있다.우리가'null'을 눌렀을 때, 우리는 우리가 이미 목록의 끝에 도달했다는 것을 알았다.이제 계수기를 2로 나누기만 하면 소수점을 얻으면 결과를 최저로 낮출 수 있다.그리고 우리는 중간값을 찾기 위해 결과의 횟수에 따라 두 번째 훑어볼 수 있다.
하지만 면접관에게 깊은 인상을 남기자.우리는 그에게 매우 복잡한 방법을 보여 주었다.우리는 로버트 W 프로이드가 제기한 거북이와 토끼 방법을 사용할 것이다.거북이와 토끼를 체인 시계 맨 앞에 놓자.토끼의 목록 이동 속도는 거북이의 두 배다.거북이는 영원히 토끼의 절반만 덮을 수 있다는 얘기다.
이제 그들로 하여금 모두 우리의 체인 시계를 두루 훑어보기 시작하게 하다.물론 토끼가 먼저 완성할 것이다.그는 링크 목록의 끝에 멈춰야만 할 것이다.그러나 토끼가 체인 시계의 끝에 도착하면 거북이는 토끼의 절반만 지나갈 것이라는 것을 우리는 안다.뭐 공부 해요?"반"은 링크 길이의 절반 또는 중간점을 나타냅니다!
현재 우리는 이미 중위수를 찾았고, 게다가 우리는 매우 효과적으로 했다.우리의 만력 방법에서, 우리는 모든 계수와 추가 시간을 두 번 반복하는 것이 아니라, 바늘 (토끼와 거북이) 을 사용하여 목록을 한 번 훑어보았다.
사진 한 장 보기:

Got it here
자, 이제 JavaScript로 코드를 작성해 보겠습니다.
우선, 첫 번째 부분의 두 가지 클래스를 다시 만듭니다. 첫째, 하나의 노드 클래스를 만들어서 하나의 노드를 만듭니다. 둘째, 하나의 SingleLinkedList 클래스는 그 안에 모든 방법을 놓을 것입니다.

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

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

이제 새로운 findMiddleElement 방법의 셸을 만듭니다.우리는 변수 "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         
  }
}

우리가 해야 할 첫 번째 일은 이 목록이 실제로 존재하는지 찾아내는 것이다. (이 엣지 사례에 대한 테스트는 당신의 면접관에게 당신이 정말 경각심을 가지고 있다는 것을 보여줄 것이다.)
간단한 방법은 머리가 있는지 없는지를 검사하는 것이다.목록에 헤더가 없으면 목록이 없습니다. "undefined"로 돌아갈 수 있습니다.(면접관에게 이런 상황에서 뭘 돌려줘야 하는지 물어보세요. 아마도 그들은 다른 것을 돌려주려고 할 거예요. 예를 들면 "-1"이나 "아이고!"

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"순환을 사용해야 합니다.
우리는 토끼가 목록의 끝에 도착할 때까지'while'순환을 실행할 것이다.토끼가 언제 도망갔는지 우리가 어떻게 알았지?두 가지 가능성이 있습니다.
1). 만약 홀수 노드가 있다면, 그가 마지막 노드에 도착했을 때, 그는 목록의 끝에 있고, 다음 노드가'null'일 때, 우리는 그가 마지막 노드에 있다는 것을 알게 될 것이다.예를 들어 7개의 노드가 있는 목록에서 그는 노드 #1에서 시작하여 한 번에 2개의 노드를 이동한다. 그는 노드 1에서 노드 3, 그리고 노드 5에서 노드 7로 이동한다.노드 7곳에서 다음 노드는null이며, 그는 어쩔 수 없이 거기에 멈출 것이다.이것은 "while"순환의 조건이 "토끼의"next"노드가"null"(hare.next!=null) 이 아니라면 계속 실행한다는 것을 의미한다

현재 짝수 노드가 있는지 여부를 고려합니다.예를 들어 8개의 노드가 있다면 우리 토끼는 노드 1부터 노드 1부터 노드 3부터 노드 5부터 노드 7까지 노드를 시작할 것이다.노드 7, 그가 두 노드를 뛰어넘을 때, 그는 목록을 떠나서'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"성명의 본문에서 우리는 우리의 영웅을 떠나게 하고 싶다!우리는 "점 다음 단계"(.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
  }
 }
}

마지막으로, 우리는 우리의 상품을 되찾을 것이다.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) {
    tortoise = tortoise.next
    hare = hare.next.next
   }

   return hare.val
 }

}

이런 거북이와 토끼의 방법은 다른 유형의 문제에서도 매우 유용하다.체인 시계나 종점, 중점, 혹은 어떤 물건이 다른 물건과 교차하는 순환을 찾으려고 시도할 때, 이런 방법을 부차적인 위치에 두어라.
면접이 즐겁고 가장 좋은 축원을 드립니다.