면접 준비: 단일 체인 테이블 끝에서 n 번째 노드 삭제

면접 준비로 돌아온 것을 환영합니다. 이 시리즈에서 우리는 데이터 구조와 알고리즘 분야에서 흔히 볼 수 있는 기술 면접 문제를 연구할 것입니다.
만약 네가 이전에 단일 체인 시계를 들어 본 적이 없다면, 너는 반드시 먼저 나의 체인 시계에 관한 기본 문장을 읽어야 한다.그렇지 않으면, 우리 계속 전진합시다!
오늘의 문제는 단일 체인 테이블을 정하고 목록 끝에서 n번째 노드를 삭제하는 것입니다.
이 문제를 이해합시다.
다음은 체인 테이블과 정수 "4"

위에서 보듯이 우리의 체인 테이블은 0에서 9개의 정수를 포함하는 노드로 구성되어 있다.헤드 노드(H)는 0, 끝 노드(T)는 9입니다.
이제 목록에서 n번째 노드를 삭제하겠습니다.우리는 n=4를 얻었기 때문에 끝에서 네 번째 노드를 삭제할 것이다.
만약 우리가 끝부분 노드나'9'에서 노드를 뒤로 계산하기 시작한다면, 끝부분에서 계산된 네 번째 노드는'6'이다.제거합시다.이제 우리의 노드는 아래의 파란색 목록과 같다.

우리 어떻게 해야 돼요?
우선, 우리가 이 문제를 어떻게 처리하는지 개념적으로 이해합시다.
우리의 첫 번째 문제는 목록 끝에서 네 번째 노드를 찾는 것이다.우리의 코드에서, 우리는 뒤로 단일 체인 시계를 훑어볼 수 없다.우리가 목록을 훑어보는 유일한 방법은 머리에서 시작하여 한 방향으로 이동하여 꼬리 뒤에'null'에 도달할 때까지 하는 것이다.
단일 체인 시계를 일방통행로로 상상하다.

하지만 걱정하지 마세요. 우리는 계획이 있어요!

우선, 목록의 시작 부분에 두 개의 바늘을 설정합시다.우리는 이 두 바늘을 "first"(F) 와 "second"(S) 라고 부른다

이제 우리는 두 번째 지침인 n의 위치를 앞으로 밀어붙입니다.우리의'n'은 4이기 때문에's'를 4위로 전진시키자.

지금 우리의 바늘은 서로 네 개의 위치를 사이에 두고 있다.
다음 단계는 각 포인터를 1 앞으로 이동하는 것입니다.우리 함께 머릿속에서 이렇게 하자.
S를 5로 앞당기기;F를 1로 앞당기다
S를 6으로 앞당기기;F를 2로 앞당기다
S를 7로 앞당기기;F를 3으로 앞당기다
잠깐만.
S가 null일 때, 우리는 전진 지침을 멈춰야 한다.이때 우리의 관점은 다음과 같다.

저거 봐!우리의 "S"포인터는 "null"로 끝나고, 우리의
F 포인터는 6에서 끝납니다.우리는 "6"이 목록의 마지막 네 번째 노드라는 것을 알아차렸다. 바로 우리가 찾아야 할 노드이다.
이제 삭제해야 할 노드를 찾았습니다. 이전 노드를'5'로 초기화하여'7'을 가리키며 삭제할 것입니다.

우리 그것을 인코딩합시다!

현재, 당신은 우리가 이 알고리즘을 어떻게 구해낼지 개념적으로 이해했습니다.우리 그것을 인코딩합시다!
우리는 체인 시계에서 머리와 꼬리만 볼 수 있다는 것을 기억하세요.그 밖에 우리는 체인 시계를 두루 돌아다니며 머리부터 꼬리로 이동할 수 밖에 없다.
우리의 함수removeNthNodeFromEnd에서는 "head"와 "n"을 매개 변수로 사용할 것입니다.

const removeNthNodeFromEnd = ( head, n ) => {


}

이제 첫 번째 포인터, 변수'first'와
두 번째 바늘, 변수'second','head'를 가리킨다.
목록에 있는 위치를 추적하기 위해 카운터 변수 (counter를 "1"으로 설정) 가 필요합니다.

const removeNthNodeFromEnd = ( head, n ) => {
  let first = head
  let second = head
  let counter = 1

}

목록에 있는 네 개의 위치를 훑어보는'두 번째'지침을 얻기 위해서, 우리는'while'순환을 사용할 것이다

const removeNthNodeFromEnd = ( head, n ) => {
  let first = head
  let second = head
  let counter = 1

  while( counter <= n ) {
     second = second.next
     counter ++
   }

}

우리 거의 다 왔어!우리는 지금'2위'가 있어'1위'보다 네 자리 앞서고 있다.
다음 단계는 목록을 훑어보는 두 개의 포인터를 시작합니다. 포인터마다 한 번씩 노드를 이동하고 서로 동기화합니다."second"가 목록의 끝에 도착하고 "null"에 도착할 때, "first"를 반복하는 것을 멈추기를 바랍니다.
근데 잠깐만!우리는 처리해야 할 작은 사건이 하나 있다.만약 "second"를 앞으로 "n"개의 위치를 추진한 후, "second"가 "null"을 가리키면 어떻게 됩니까?그것은 보기에 이렇다.

"S"가 "null"에 있는 것을 보았습니다. "F"에서 삭제해야 하는 노드는 사실상 헤더 노드입니다.우리는 어떤 중간 노드를 제거하는 것처럼 머리 노드를 제거할 수 없다.헤드 노드를 제거하면 헤드 노드를 다음 노드로 재설정해야 합니다.우리의 예시에서 새로운 두절점은 "1"이다.엣지 사례를 살펴보겠습니다.

const removeNthNodeFromEnd = ( head, n ) => {
  let first = head
  let second = head
  let counter = 1

  while( counter <= n ) {
     second = second.next
     counter ++
   }

   //edge case if second points to “null”:
 if ( second === null ) {
 // update value of the head node 
 head.value = head.next value

 //update the pointer of the head node:
 head.next = head.next.next

// and we’re done.  Let’s just exit the function
return head
   }



}

기왕 변의 상황이 이미 해결되었으니, 우리는 모든 바늘을 목록을 두루 훑어보도록 하자.그러나, "second"가 "null"이전의 마지막 노드에 도착했을 때, 우리는 반복을 멈추기를 희망합니다.
이것은'첫 번째'가 우리가 진정으로 없애고 싶은 노드에 도착하기 전에 이 노드에 도착한다는 것을 의미한다.
우리의 지침은 다음과 같다.

우리는 왜 이렇게 합니까?좋아, 노드 사이의 연결을 밧줄의 작은 매듭으로 상상해 봐.만약 우리가 정말로 없애고 싶은 "6"을 두루 훑어보고 그것을 "풀다"에서 "7"으로 묶으면, 우리는 "7"에 대한 인용을 잃게 될 것이다.'7'이 목록의 나머지 부분과 연결되지 않으면'부동'이 떨어진다고 상상해 보세요.
우리가'6'에서 벗어나야 할 방법은 이전 이웃을 통과하는 것이다.'5'
지금 우리가 해야 할 일은'first'가'5'를 가리킬 때'retie'5의'next'를 7로 묶는 것이다.상상해봐.너는 이 과정에서 아무것도 풀리지 않은 것을 보게 될 것이다.일단 우리가 5와 7을 한데 묶으면, 지금 우리는 6을 7에서 안전하게 풀 수 있다.그리고 이 여섯 개는 컴퓨터가 무한히 먼 곳으로 떠다닐 수 있다.
우리 합시다."second"가null이 아니라면, 나는 두 개의 바늘을 추진하기 위해 코드를 작성할 것이다.

const removeNthNodeFromEnd = ( head, n ) => {
  let first = head
  let second = head
  let counter = 1

  while( counter <= n ) {
     second = second.next
     counter ++
   }

   //edge case if second points to “null”:
 if ( second === null ) {
 // update value of the head node 
 head.value = head.next value

 //update the pointer of the head node:
 head.next = head.next.next

// and we’re done.  Let’s just exit the function
return head
   }

       // now we advance each pointer. Let’s
       // keep going so long as second IS NOT null
       while ( second. next !== null ) {

           second = second.next
           first = first. next
       }


}

우리 이제 마지막 코드만 남았어!
우리는 위에서 설명한'retying'만 하면 된다.우리의 첫 번째 지침은 5, 6 이전의 노드 - 우리가 없애고 싶은 노드이다.우리는 우리가 6 또는 7 이후에 5를 노드에 재설정하기만 하면 된다는 것을 안다.
우리는 어떻게 5와 7을 다시 귀속합니까?
우리는 단지 다음과 같이 할 뿐이다.

      first.next = first.next.next

표현식의 오른쪽에서 "first"는 "5"로 설정됩니다.이것은 우선을 의미한다.다음은'6'과 첫 번째입니다.다음다음은'7'입니다."7을"first"또는"5"다음 노드로 설정합니다.
아래의 최종 코드를 보십시오

const removeNthNodeFromEnd = ( head, n ) => {
  let first = head
  let second = head
  let counter = 1

  while( counter <= n ) {
     second = second.next
     counter ++
   }

   //edge case if second points to “null”:
 if ( second === null ) {
 // update value of the head node 
 head.value = head.next value

 //update the pointer of the head node:
 head.next = head.next.next

// and we’re done.  Let’s just exit the function
return head
   }

       // now we advance each pointer. Let’s
       // keep going so long as second IS NOT null
       while ( second. next !== null ) {

           second = second.next
           first = first. next
       }

      first.next = first.next.next

     // does the interviewer want us to return something?
}

면접관에게 물어보겠습니다. 만약 있다면, 그들은 우리가 돌아와서 무엇을 하기를 원합니다.그렇게 지도 모른다, 아마, 아마...그렇게 지도 모른다, 아마, 아마...어쩌면 그냥 "내가 해냈어! 예!"

공간 및 시간의 복잡성

우리는 단지 목록을 한 번 훑어보았을 뿐이다.중첩 순환이 없기 때문에 우리는 O(n) 시간 복잡도가 있다
우리는 우리의 알고리즘으로 어떠한 새로운 데이터 구조도 만들지 않을 것이다.우리의 모든 조작은 같은 목록에서 이루어지기 때문에 우리의 공간 복잡성은 매우 멋진 O(1)
여기 있습니다.이것은 하나의 체인 테이블의 끝에서 노드'n'개의 위치를 삭제하는 데 사용되는 재미있고 상대적으로 간단한 알고리즘이다.
당신의 인터뷰가 즐겁고 가장 좋은 축원을 드립니다.