연결 리스트 손코딩 문제들

문제 1

원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 풀이를 효율적으로 구하는 방법은?

 

정답

동일한 노드가 나올때까지 계속 다음 노드로 가면 된다.  공간 복잡도 O(1), 시간 복잡도 O(N).

 

 

문제 2

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

정답

일단 두 시작점 각각에 대하여 끝까지 진행시켜서 각각의 길이를 구한다. 그 후 다시 시작점으로 돌아와서 더 긴 쪽을 둘의 차이만큼 앞으로 먼저 이동시켜 놓고, 두 시작점이 만날 때까지 두 시작점을 동시에 한 칸씩 전진시키면 된다.

공간 복잡도 O(1), 시간 복잡도 O(A+B).

 

 

문제 3 

주어진 연결 리스트 안에 사이클이 있는지 판단하라.

정답

Floyd's cycle-finding algorithm 을 사용하면 판단이 가능하다.

snutiise.github.io/Floyd's-Cycle-Detection-Algorithm/

플로이드 순환 찾기 알고리즘 Floyd's Cycle Detection Algorithm

한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발시키면 사이클이 있는 경우 반드시 만나게 된다.

반대로 만약 사이클이 없으면 두 커서가 만나지 못하고 연결 리스트의 끝에 도달하지 못하게 된다.

이 방식으로 사용하면 거치는 모든 노드를 저장할 필요 없이 공간 복잡도 O(1)에 사이클의 존재 여부를 확인할 수 있다.

 

공간 복잡도 O(1), 시간복잡도 O(N)