728x90

Q. Linked Lists의 마지막 Node에서 n번째 앞에 Node를 반환하는 function을 작성하라.

---Examples;
const list = new List();
list.insertLast('a');
list.insertLast('b');
list.insertLast('c');
list.insertLast('d');
fromLast(list, 2).data; // 'b'

🎈첫 번째에서부터 다음 n번째 Node와, 마지막에서부터 앞으로 n번째 Node의 간격은 같다. 생각의 전환!
을 생각하면 조금 더 쉽게 풀어나갈 수 있다.

From Last 힌트 및 이미지화

🧨 역시나 앞서 풀었던 2문제들과 비슷하다. 하지만, 생각을 조금 다르게 해야한다.
뒤에서부터 3번 앞으로 이동하면 red Node이며, 마지막 Node는 grey이고, 간격은 3이다.
앞에서부터 3번 뒤로 이동하면 orange Node이며, 첫 번째 Node는 green이고, 간격은 3이다.

만약, slow와 fast가 시작점(green)에서 시작할 때, fast를 먼저 3번 앞으로 이동해보자.
그럼 fast는 orange를 만난다. slow는 시작점인 green을 가리키고 있다.
이제 fast가 끝(grey)에 도달할 때까지, slow와 fast를 1칸씩 이동해보자.
slow는 최종적으로 red를 가리키게 된다.

즉, 앞에서 이동하나 뒤에서 이동하나 그 간격은 같다. Node를 각각 반대로 생각하면 된다.
결과적으로, fast는 마지막 node를, slow는 뒤에서부터 n번째 떨어진 node를 의미하게 된다.

이렇게 뒤에서 앞에 n번째 값을 구할 수 있다.

slow와 fast 진행도
From Last 정답 코드

🔮 while loop을 이용해 fast를 n만큼 이동시켜주고, 또 다시 while loop을 이용해 slow와 fast를 이동시켜준다.
결과적으로 slow는 뒤에서 n번째 Node를 가리키게 된다.

Full Code

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;
}

+ Recent posts