728x90

Q. Linked Lists의 중간 Node를 찾는 function을 구현하라.
(매개변수로 list를 받으며, Lists의 크기가 짝수라면, Lists 반의 앞 부분에서 마지막 Node를 반환하고,
counter변수나 size() method를 사용하지 않고 풀어야 한다)

🎈 토끼와 거북이의 경주를 생각해보자.
토끼가 거북이의 2배 속도로 달린다고 생각할 때, 토끼가 도착하면 거북이는 중간을 달리고 있을 것이다.

토끼 변수1, 거북이 변수1, 달리기 반복 loop을 이용해서 문제를 해결해보자.

Find the Midpoint 힌트 및 이미지화

 

🧨 slow와 fast변수는 같은 시작점에서 출발한다. 그리고 slow는 1칸씩, fast는 2칸씩 이동한다.
Lists 크기가 홀수일 경우를 먼저 생각해보자.
fast가 2칸씩 이동했을 경우, 항상 마지막 Node에 도착할 수 있고, 그때 slow의 위치는 중간이다.
하지만, Lists의 크기가 짝수일 경우에는 fast가 마지막 Node에 도착할 수 없다.
따라서, fast의 다음 칸은 있지만, 다음 다음 칸을 확인했을 때 Node가 없다면
그때 slow의 위치는 중간(즉, Lists 전체 크기에서 반을 잘랐을 때 앞부분 반의 마지막 Node)이다.

위의 내용을 아래 코드로 옮겨 보았다.

정답 코드

🔮 slow나 fast를 초기화할 때, list.head;를 사용해도 동일하며, while의 조건은 반드시 &&(and)로 넣어줘야 한다.

Full Code

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

+ Recent posts