기록하는 공간

Fast and Slow pointer 정리

17 Apr 2023

Linked List Cycle

알고리즘 문제를 풀고 나서는 항상 다른 풀이를 보곤 한다. 다른 사람의 풀이에서 배울 수 있는 게 정말 많다. Linked List Cycle은 링크드 리스트의 헤드가 주어질 때, 해당 링크드 리스트가 사이클을 이루는지 확인하는 문제이다. 노드의 다음 값이 있을 경우, 계속 탐색하고 그럴 때마다 이미 확인한 값인지 보도록 해서 문제를 풀도록 했다.

class ListNode(var `varl`: Int) {
  var next: ListNode? = null
}

class Solution {
    fun hasCycle(head: ListNode?): Boolean {
        val checked: MutableList<ListNode> = mutableListOf()
        var current = head
        
        while (current != null) {
            if (checked.contains(current)) {
                return true
            }
            checked.add(current)
            current = current.next        
        }
        
        return false
    }
}

위의 풀이로 통과는 했지만, 런타임 성능에서는 매우 좋지 않았다. 다른 풀이를 보던 중 fast와 slow라는 변수를 선언해서 푼 풀이가 많이 보였고 검색해보니 fast and slow pointers라는 방법이라는 걸 알게 되었다.

Fast and Slow Pointers

이 알고리즘은 이름 그대로 두 개의 포인터를 두어서 반복 가능한 자료구조나 배열 등을 검색할 사용한다. 느린 포인터는 한 번에 한 단계식 더 느리고, 빠른 포인터는 한 단계씩 더 빠르게 이동한다. 두 포인터는 같은 방향으로 이동하지만, 다른 속도로 이동한다.

위의 문제 같은 경우는, 두 포인터가 다른 속도로 움직이다가 결국 같은 노드에서 만나게 될 경우 사이클의 존재를 확인할 수 있게 된다. 이 알고리즘을 이용해서 풀면 아래와 같이 된다.

class Solution {
  fun hasCycle(head: ListNode?): Boolean {
    var fast = head
    var slow = head
    
    while (slow?.next != null && fast?.next?.next != null) {
      fast = fast.next.next
      slow = slow.next
      
      if (slow == fast) return true
    }
    return false
  }
}

Related Posts