중간 노드 찾기(Find the Middle Node)

References

아래 링크의 강의 중 Section 22. Find the Midpoint의 내용을 추려 이번 글을 작성하였습니다.
The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Solution

function midpoint(list) {
  let slow = list.getFirst();
  let fast = list.getFirst();

  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow;
}

linked list를 한 칸씩 탐색하는 변수 slow와 두 칸씩 탐색하는 변수 fast를 각각 선언한다. fast로 탐색을 하다 더 이상 탐색값이 없다면(null) while문을 멈추고 linked list의 중간값인 slow를 반환한다.