728x90

Q. Linked Lists가 circular인지 확인하라(마지막 Node가 없고, 계속 순환하는 Linked List).
(맞다면 true, 아니라면 false를 반환)

--- Examples
const l = new List();
const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
l.head = a;
a.next = b;
b.next = c;
c.next = b;
circular(l) // true

🎈 토끼와 거북이가 운동장 돌기 경주를 하는데, 경주의 끝이 없다면, 언젠가는 둘이 만날(겹칠) 것이다.
라고 상상하면 조금 더 쉽게 풀어나갈 수 있다.

Check Linked List Circular 힌트 및 이미지화

🧨 앞서 풀었던 Find the Midpoint 문제를 응용하면 된다.
slow와 fast의 시작점은 같고, slow는 1칸, fast는 2칸씩 이동한다.
계속 이동하다보면 slow === fast가 되는 경우가 발생할 것이고, 이걸 조건문으로 넣어 true를 return하면 된다.
만약, circular가 아니라면 while loop조건 fast.next.next를 만족하지 않으므로 while loop이 끝난 후 false를 return하면 된다.

Check Linked List Circular 정답

🔮 while loop안에서 slow === fast 조건을 넣어주고, true가 반환된다면 이 Linked List는 Circular(순환)이며,
while loop의 조건인 fast.next.next를 만족시키지 못한다면 끝이 있는 Linked List이므로 Circular가 아니다.

Full Code

function circular(list) {
let slow = list.getFirst();
let fast = list.getFirst();
 
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
 
if (slow === fast) {
return true;
}
}
 
return false;
}

+ Recent posts