순환 리스트(Circular List)

References

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

---

Solution

function circular(list) {
  let slow = list.getFirst(); // = list.head;
  let fast = list.getFirst();

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

    if (slow === fast) {
      return true;
    }
  }

  return 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

이전에 작성한 중간 노드 찾기와 코드 구성이 유사하다. slow와 fast 변수가 각각 linked list를 탐색하다가 두 값이 모두 똑같은 node를 가리키게 되면 true를 반환하고, 조건을 만족하지 못하면 false를 반환하게 된다.

---

---

함께 보기

Linked Lists