끝에서부터 노드 세기(From the Tail)

References

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

---

Solution

function fromLast(list, n) {
  let slow = list.getFirst();
  let fast = list.getFirst();

  while (n > 0) {
    fast = fast.next;
    n--;
  }

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

  return slow;
}

눈여겨봐야 할 부분은 두 개의 while문의 기능이다.

첫 번째 while문

n이 0보다 클 동안 while문을 돌면서 변수 fast를 한 칸씩 앞으로 전진시킨다. 결과적으로 변수 fast에 할당된 node의 위치는 변수 slow에 할당된 node보다 n만큼 앞서게 된다.

두 번째 while문

fast.next가 true인 동안 변수 slow와 fast 한 칸씩 전진시킨다. fast.next의 값이 null이 되는 지점이 곧 tail을 뜻하므로 이 때의 slow는 곧tail에서 n만큼 떨어진 node와 같다.