[알고리즘/자바스크립트] 환영 연결 리스트 찾기 (Linked List Cycle)

Linked List Cycle

Generally, we assume that a linked list will terminate in a null next pointer, as follows:

 

A -> B -> C -> D -> E -> null

 

A 'cycle' in a linked list is when traversing the list would result in visiting the same nodes over and over

This is caused by pointing a node in the list to another node that already appeared earlier in the list. Example:

 

A -> B -> C

       ^     |

        |     v

       E <- D

 

var nodeA = Node('A');
var nodeB = nodeA.next = Node('B');
var nodeC = nodeB.next = Node('C');
var nodeD = nodeC.next = Node('D');
var nodeE = nodeD.next = Node('E');

hasCycle(nodeA); // => false
nodeE.next = nodeB;
hasCycle(nodeA); // => true

 

일반적인 형태의 linked list는 tail이 null이다.

그런데 만약 tail이어야할 linked list가 그 이전의 linked list를 가리키고 있다면

그건 끝없이 순환하는 형태가 될 것이다.

 

 

이런 형태의 linked list를 Circular Linked List, 환영 연결 리스트라고 부른다.

linked list가 파라미터로 주어졌을 때 그것이 circular인지 아닌지 확인하는 메소드를 만드는 알고리즘을 풀어보자.

 

 

---

 

 

  const listLog = [];
  const alreadyPassed = (cur) => listLog.includes(cur);

  while (linkedList.next) {
    if (alreadyPassed(linkedList)) {
      break;
    }

    listLog.push(linkedList);
    linkedList = linkedList.next;
  }

  return linkedList.next !== null

 

내가 생각해낸 방법은 그냥 일반적으로 사람들이 가장 처음 떠올릴만한 쉬운 방법이다.

배열을 하나 만들어서 연결 리스트를 순차적으로 넣고 매번

이미 지나간 연결 리스트가 배열에 존재하는지 아닌지 확인하여 판단하는 방법이다.

분명 이것보다 더 좋은 방법이 있을텐데 도저히 생각이 안나서 일단 이렇게 풀어놓고 인터넷을 찾아보았다.

 

 

Floyd’s Tortoise and Hare algorithm

 

 

역시나 Floyd’s Tortoise and Hare algorithm을 사용한 매우 간단한 방법이 있었다.

먼저 Tortoise(거북이)이는 느리게 움직인다. Hare(토끼)는 빠르게 움직인다.

먼저 거북이가 0번째에서 출발한다면, 토끼는 그 다음 칸인 1번째에서 출발한다.

거북이가 1칸을 이동하면 토끼는 2칸을 이동한다.

이것을 반복하여 이동하다보면 만약 이 리스트가 순환하고 있다면 언젠가 토끼와 거북이는 반드시 만난다.

바로 이것이 이 알고리즘 문제의 해결책이다.

 

 

let slowPointer = linkedList;
let fastPointer = linkedList.next;

while (fastPointer.next.next) {
  if (slowPointer === fastPointer) {
    return true;
  }
  slowPointer = slowPointer.next;
  fastPointer = fastPointer.next.next;
}

return false;

 

알고리즘 원리를 알고 다시 풀어본 나의 해답이다.

 

 

 

 

---

참고자료:

https://medium.com/@joshuablankenshipnola/checking-for-linked-list-cycles-in-javascript-77ec9adc6822

Checking For Linked List Cycles in JavaScript