연결리스트 손코딩 문제 - barking dog님

물론 방법은 여러가지겠지만 최소한의 공간복잡도와 시간복잡도를 고려한 방법을 생각해야한다.

1.원형 연결리스트 내 임의의 노드가 하나 주어졌을 때 해당 list의 길이를 구하는 방법?

동일한 노드가 나올때 까지 순회하면 됨. 공간복잡도O(1), 시간 복잡도 O(N)

2.중간에 만나는 두 연결리스트의 시작점들이 주어졌을 때, 만나는 지점을 구하는 방법?

(나가면서 스치는 모든 노드를 저장하지 말고, 먼저 둘의 길이 차이를 구한 다음에 더 긴 쪽을 차이만큼 이동시켜놓으면 이제는 둘을 동시에 한 칸씩 당겼을 때 만나는 지점을 구할 수 있게 될 것입니다.)
일단 두 시작점 각각에 대해 끝까지 진행시켜 각각의 길이를 구함.
그 후 더 긴쪽을 두 길이의 차이만큼 앞으로 당기고 두시작점이 만날 때까지 동시에 한칸씩 움직이면서 찾으면됨.
공간복잡도O(1), 시간 복잡도 O(A+B)

3. 주어진 연결리스트에 사이클이 있는지 판단하는 방법.

플로이드 서클 알고리즘을 이용하면 됨. 공간복잡도O(1), 시간 복잡도 O(N)

• 이 문제는 Floyd's cycle-finding algorithm이라는 이름이 붙어있는 알고리즘으로 해결이 가능한데, 한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발시키면 사이클이 있을 경우 두 커서는 반드시 만나게 됩니다. 반대로 만약 사이클이 없으면 두 커서가 만나지 못하고 연결 리스트의 끝에 도달합니다. 이 방식을 이용하면 거치는 모든 노드를 저장할 필요가 없이 공간복잡도 O(1)에 사이클의 존재 여부를 알 수 있습니다. -바킹독센세