연결 리스트에서 루프의 길이 찾기

코딩 기술을 향상시키기 위해 일부 katas를 수행했습니다. 저는 지금 6kyu on CodeWars 에 있습니다.
이번 주 내 흥미로운 문제는 다음과 같습니다.

연결된 목록의 시작 노드가 제공됩니다. 이 목록에는 항상 테일과 루프가 포함됩니다. 귀하의 목표는 루프의 길이를 결정하는 것입니다. 루프는 다음과 같습니다.

해결 방법

이 질문에는 두 부분이 있습니다.

루프에 있는 경우 파악

루프의 노드 수 계산

루프에 있을 때 그림

빠른 구글 검색 후, Floyd의 주기 감지 알고리즘을 발견했습니다. 이 알고리즘은 루프에 갇혔는지 여부를 찾습니다. 또한 이를 사용하여 루프의 시작 위치를 정확히 찾을 수 있지만 이는 이 질문의 범위를 벗어납니다.

기본 아이디어는 2개의 포인터가 있다는 것입니다.

다음 노드로 1씩 이동하는 것(느린 포인터)

2노드씩 이동하는 두 번째 포인터(빠른 포인터)

당신이 속한 목록이 실제로 루프라면, 둘 다 빙글빙글 돌기 때문에 둘 다 어느 시점에서 만나야 합니다.

따라서 코드는 다음과 같습니다.

function getNodeInLoop(node){
   let slow = node;
   let fast = node.next;

//problem assumes there is always going to be a loop
//so no need to check
   while(slow !== fast){ 
        slow = slow.next; //move by 1
        fast = fast.next.next; //move by 2
    }

  return slow; 
}

따라서 루프에서 노드의 알려진 위치를 반환합니다.

세다

노드 수를 세기 시작할 수 있습니다! 느린 포인터와 빠른 포인터가 모두 일치하는 노드(여기서는 seenNode)를 루프의 루트 노드로 취급합니다. "포인터"변수를 사용하여 우리가 while 루프에 있는지 추적하고 "카운트"를 사용하여 통과한 노드 수를 계산합니다.

    let size = 1
    let seenNode = getNodeInLoop(node); 
    let pointer = seenNode.next; 

    while(pointer !== seenNode ){
        size++; 
        pointer = pointer.next;
    }

    return size;

해결책

전체 솔루션은 다음과 같습니다.

function loop_size(node){
    let size = 1;
    let seenNode = getNodeInLoop(node); 
    let pointer = seenNode.next; 

    while(pointer !== seenNode ){
        size++; 
        pointer = pointer.next;
    }

    return size;
}

function getNodeInLoop(node){
   let slow = node;
   let fast = node.next;

//problem assumes there is always going to be a loop
//so no need to check
   while(slow !== fast){ 
        slow = slow.next; //move by 1
        fast = fast.next.next; //move by 2
    }

  return slow; 
}

짜잔!

연결

CodeWars Question

p.s 이유는 모르겠지만 codewars는 솔루션에 대한 별도의 기능을 좋아하지 않으므로 대부분의 코딩 솔루션은 하나의 기능으로 작성됩니다.
p.p.s 항상 그렇듯이 이것은 내 솔루션일 뿐이며 다른 구현이 있다는 것을 알고 있습니다. 토론을 시작하려면 자유롭게 댓글을 달아주세요 :) !