Runner 기법

Runner 기법은 일반적으로 링크드 리스트(linked list)와 같은 자료구조에서 사용되는 두 포인터(tortoise and hare) 기법입니다. 이 기법은 다양한 문제를 효율적으로 해결하는 데 유용합니다. 대표적인 예로는 사이클 검출, 중간 지점 찾기, 두 리스트의 교차점 찾기 등이 있습니다. 가장 널리 알려진 것은 Floyd의 사이클 탐지 알고리즘입니다.

1. Floyd's Cycle Detection Algorithm

Floyd의 알고리즘은 주로 링크드 리스트에서 사이클이 존재하는지 확인하는 데 사용됩니다. 이 알고리즘은 다음과 같이 작동합니다:

• 두 포인터 설정: 두 개의 포인터를 설정합니다. 하나는 'slow' 포인터, 다른 하나는 'fast' 포인터입니다.
• 포인터 이동:
  • slow 포인터는 한 번에 한 노드씩 이동합니다.
  • fast 포인터는 한 번에 두 노드씩 이동합니다.
• 사이클 확인: 만약 리스트에 사이클이 존재한다면, 두 포인터는 결국 만나게 됩니다. (사이클 안에서 회전하다 보면 반드시 만납니다.)
• 종료 조건:
  • fast 포인터나 fast 포인터의 다음 노드가 null에 도달하면 사이클이 없다는 뜻입니다.
  • slow 포인터와 fast 포인터가 만나면 사이클이 있다는 뜻입니다.

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return true;
    }
}

 

 

 

2. 중간 지점 찾기

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public ListNode findMiddle(ListNode head) {
        if (head == null) {
            return null;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
}