중간 지점 찾기

• Reference
• 총 3가지 방법으로 마지막 방법에 유의해보고자한다.
• 1 3 5 7 9 면, 5가 중간 지점이다.
• 1 3 5 7 이면 5가 중간 지점이다.

Algorihtm

Node1 -> Node2 -> ... -> Noden

• n 번 순회 후 counting 하여 length를 알아내고 n/2 만큼 원소로 이동한다.
• TimeComplexity : O(n)
• SpaceComplexity : O(1)

Node1 -> Node2 -> ... -> Noden

Arr1, Arr2, Arr3 ... Arrn

• Array에 Node 또는 값을 담으면서 length를 호출해 size를 알고, random access를 하면 된다.
• TimeComplexity : O(n)
• SpaceComplexity : O(n)
• One Pass 방법이다.
  • 리스트로만 풀면, 다시 중간지점으로 원소 이동해서 접근해야된다.

Node1 -> Node2 -> ... -> Noden
fastPtr
slowPtr

Node1 -> Node2 -> Node3 -> ... Noden
				 fastPtr
		slowPTr

• 1칸 씩 앞서나가는 slowPtr, 2칸 씩 앞서나가는 fastPtr을 통해 fastPtr이 마지막을 지나면, slowPtr의 위치가 중간지점이다.
• 리스트 문제에서 많이 나오므로 숙지해놓는 것이 좋을 것 같아 기록한다.