면접 준비: 역방향 체인 알고리즘

면접 준비 단계로 돌아온 것을 환영합니다. 오늘 우리는 매우 유행하는 체인 시계에 관한 면접 문제를 보겠습니다.
만약 당신이 체인 시계의 기본 지식을 이미 알고 있다면, 계속 읽어 주십시오.만약 없다면, 나의 체인 테이블 기초 문장부터 시작하세요.
링크 테이블 글의 기초:

문제는 무엇입니까?

우리는 다음과 같은 링크 목록을 얻었다.

이것은 다섯 개의 노드가 있는 체인 시계다.각 노드는 정수 1-5를 포함합니다.이 목록에서 1대 2.2 대 3.3대 4, 4대 5.1은 목록의 "머리", 5는 목록의 "끝"
지금 우리는 목록의 링크를 반전시켜 아래의 녹색 링크처럼 보이고 싶다

위의 그림에서 녹색 체인 시계가 반전되었습니다.5 지금은 머리, 지향 4.4 이제 3을 가리키고 있다.0은 이제 끝입니다.
어떻게 해요?
알겠습니다. 원본 목록을 반전시키려면 각 노드의'다음'속성과 관련이 있을 것입니다.네, 맞아요.까다로운 것은 우리가 한 노드의'다음'속성을 반전시키고 이전 노드를 가리키게 할 때, 우리는 이전의 다음 노드에 대한 인용을 잃게 된다는 것이다.내 말은:
체인 시계 하나 더 봅시다.이번에는 세 개의 노드만 있다. 하나, 둘, 셋.우리는 2의'next'속성을 취하여'1'을 가리키고 싶습니다.아래에서 나는 분홍색으로 화살표를 동그라미하여 우리가 반전시키고 싶은'다음'속성을 대표한다

위의 두 번째 줄에서 나는 2의 "next"속성을 이전 구성원인 "1"으로 설정했다.그러나 보시다시피 현재 "3"을 가리키는 화살표가 없습니다."3"은 현재 우리의 링크 목록에 없습니다.
그러면 체인 시계를 반전시킬 때 우리는 어떻게 인용을 잃어버리는 것을 피할 수 있습니까?
포인터 사용
우리가 해야 할 일을 설명하기 위해서, 나는 목록의 중간부터 사진 한 장을 사용할 것이다.이렇게 하면 더욱 형상화하기 쉽다.(예, 우리가 진정한 코드를 시작할 때, 우리는 목록의 시작부터 시작할 것입니다. 마찬가지로, 지금은 가장자리 상황을 걱정하지 마십시오.)
5개의 노드가 있는 흰색 체인 테이블로 돌아가겠습니다.

너는 내가 파란색 바늘을 추가한 것을 알아차릴 것이다.P2, 현재 값이 3인 노드가 주 이벤트입니다!'next'속성을 반전시키려고 합니다. (그림에서 화살표로 표시합니다.)"next"속성을 조작할 때 인용을 잃지 않기 위해서, 현재 값이 2인 노드에 있는 P1을 다시 설정합니다.
이 문제를 해결하는 데는 4단계가 있다.
우리는 여전히 하나의 지침만 남았고, 하나의 P3는 P2 노드 이후의 노드를 가리킨다.
우리는 p3를 p2로 설정합니다.다음 단계:

P2를 설정합니다.그 전신 "1"옆

위에서 분홍색을 볼 수 있습니다. 저는 P2의'다음'속성을 뒤바꿨습니다.P2는 지금 P1을 가리키고 있습니다. 우리가 원하는 것처럼.
그럼 이제 어떡하지?우리는 어떻게 체인 시계를 계속 훑어봅니까?
우리는 바늘을 계속 이동해야 한다.사실 주요 논리를 완성하려면 두 가지 절차가 있다!
P1을 P2로 설정하려면:

위에서 P1을 새로운 위치로 옮긴 것을 보실 수 있습니다
마지막 단계: 이제 P2를 P3로 설정합니다.

여기에 체인 시계의 교체가 있다.
그러나 우리가 코드를 토론하기 전에, 나는 당신에게 P3가 어떻게 위치를 이동하는지 보여주고 싶습니다.
우리는 단지 위의 단계 1-4에서 완전한 교체를 진행했을 뿐이다.우리는 지금 두 번째 교체를 시작할 준비를 하고 있다.우리 첫걸음으로 돌아가자.첫 번째 단계에서 P3를 P2로 설정합니다.다음은 다음과 같습니다.

너희는 우리가 이미 위의 4단계에서 P2를 P3의 위치로 옮겼다는 것을 기억할 것이다.따라서 우리는 새로운 P3를 P2의 다음 속성으로 설정할 수 있다.
지금 코드예요.
우리가 인코딩을 시작하기 전에 단지 하나의 알림일 뿐이다.
P2 바늘은 우리의 별 모양 바늘로 우리의 코드는 그것에 적응하도록 구성될 것이다.
2) 우리 최초의 5개 노드가 있는 체인 시계에서'1'이전과'5'이후가 무엇인지 아십니까?예, 맞습니다. 없음 또는 "null":

그 밖에 우리는 항상 체인 시계의 길이를 확정하지 않기 때문에 우리는'while'순환을 사용하도록 한다."성형"포인터 P2가 목록에서 뛰어나와 "null"

에 도달할 때까지 계속 순환할 것입니다

작은 문제는 "이 목록은 무엇을 되돌려야 합니까?"이것은 면접관에게 묻는 좋은 문제다.아마 그들은 반품하고 싶지 않을 거야!이제 P1로 돌아가자. 우리는 할 수 있으니까!

네, 인코딩해 보겠습니다.

// Declare our function and pass it our linked list’s head // 
// node

const reverseLinkedList = head => {
      // our p2 is the star pointer.  Let’s 
set it to the head
     let p2 = head
    // p1 comes BEFORE P2.  But if p2 is the head,
   //  what can come before the head?  Must be “null”
    let p1 = null

  // Here’s our while loop.  We’ll keep looping 
 // so long as P2, our star, doesn’t fall off the linked list
// and get to “null”
    while ( p2 !== null) {
        let p3 = p2.next   //step 1
        p2.next = p1       //step 2
        p1 = p2              //step 3
        p2 = p3              //step 4
    }
    return p1          //This imaginary interviewer wanted
                               // me to return P1.  Go figure!
}

나는 공간과 시간의 복잡성을 토론하기 시작해야 한다.
이 알고리즘에서 우리의 시간 복잡도는 O(n)이다. 왜냐하면 우리는 목록을 한 번만 훑어보았기 때문이다.
공간의 복잡성은 우리의 모든 조작이 제자리에서 진행되기 때문에 매우 멋진 O(1)이다.예를 들어 우리는 새로운 체인 테이블이나 다른 대상을 만들지 않았습니다. 이것은 더 많은 메모리 공간을 차지할 것입니다.
이것은 유행하는 체인 면접 문제의 해결 방안이다.이제 너는 그들을 때려죽일 수 있어!
즐겁게 놀다
계속 당신의 꿈을 인코딩하세요!
나마스트!
탕니