Middle of the Linked List

이 문제에서 포인터는 노드 인덱스입니다. 다음 노드로 이동하는 것은 node = next[node]이며, -1에 도달하면 끝을 벗어난 것입니다. 첫 번째 예제에서 노드 0부터 순회하면 0 → 3 → 4 → 2 → 1 → -1이 됩니다.

리스트의 문제는 특정 위치로 건너뛸 수 없다는 것입니다. 그러니 건너뛸 수 있도록 바꿔 봅시다. 리스트를 한 번 순회하면서 각 값을 지나칠 때마다 새 배열에 추가합니다. 이 배열에는 리스트 순서대로 값이 담기며, 첫 번째 예제에서는 [4, 7, 5, 2, 9]가 됩니다. 배열의 가운데는 정수 나눗셈을 사용한 인덱스 length / 2입니다.

이 인덱스만으로도 길이가 짝수일 때 두 번째 가운데 값을 구할 수 있습니다. 값이 6개라면 인덱스는 3이고, 이는 두 번째 예제에서 40인 네 번째 값입니다. 순회에는 O(n) 시간이 들고 복사에는 O(n)의 추가 메모리가 필요하지만, 다음 두 가지 접근 방식은 이를 피합니다.

전체 복사본은 필요 없고 길이만 알면 됩니다. 리스트를 한 번 순회하며 노드 수를 세세요. 그런 다음 다시 헤드에서 시작해 length / 2만큼 내림하여 이동합니다. 멈춘 노드가 중간 노드입니다.

이만큼 이동하는 이유는 다음과 같습니다. k번 이동하면 헤드를 위치 0으로 세었을 때 위치 k에 있는 노드에 도달합니다. 5개 노드가 있는 리스트의 중간은 위치 2이고, 6개 노드가 있는 리스트의 두 번째 중간은 위치 3이며, 둘 다 length / 2입니다. 첫 번째 예시에서는 5를 센 다음 두 번 이동해 0 → 3 → 4로 가고, values[4] = 5를 읽습니다.

이제 메모리 사용량은 O(1)입니다. 그 대가로 리스트의 절반을 한 번 더 순회해야 하며, 총 이동 횟수는 1.5n입니다. 그래도 여전히 O(n)입니다.

두 포인터를 헤드에 둡니다. 각 라운드마다 slow는 노드 하나를 이동하고 fast는 두 노드를 이동합니다. k라운드가 지나면 slow는 위치 k에 있고 fast는 위치 2k에 있으므로, slow는 항상 fast가 이동한 거리의 절반을 이동한 셈입니다. fast가 끝에 도달하면 slow는 가운데에 있으며, 길이를 알 필요가 없습니다.

중단 규칙에 따라 어느 쪽 가운데를 얻을지가 결정됩니다. fast가 실제 노드이고 그다음 노드도 있는 동안 계속 진행합니다. 즉, fast != -1이고 next[fast] != -1인 동안입니다. 길이가 홀수이면 fast는 마지막 노드에서 멈춥니다. 길이가 짝수이면 fast는 끝을 벗어나 -1이 되고, 이로 인해 slow가 한 번 더 이동하여 두 가운데 중 뒤쪽에 도달합니다. 두 번째 예시에서 slow는 0, 1, 2, 3으로 이동하고 fast는 0, 2, 4, -1로 이동하며, values[3]은 40입니다.

첫 번째 예시에서 slow는 노드 0, 3, 4를 방문하고 fast는 0, 4, 1을 방문합니다. 노드 1이 마지막 노드이므로 루프는 slow가 노드 4에 있을 때 멈추고 답은 5입니다. fast는 약 n번 이동하고 slow는 n / 2번 이동하므로, 메모리로 정수 두 개만 사용해 한 번 순회합니다.