런너 기법

런너는 연결리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법이다.
빠른 런너, 느린 런너 두개의 포인트를 사용한다.

병합지점이나 중간 위치 길이등을 판별할때 유용하게 사용할 수 있다. 주로 중간을 기준으로 값을 비교하거나 뒤집기를 시도하는 등 연결리스트 문제에서 자주 사용하는 기법

릿코드 235

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        rev = None
        slow = fast = head
        # 런너를 이용해 역순 연결 리스트 구성
        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
        if fast:
            slow = slow.next
        
        # 느린 러너를 마저 돌리며 팰린드롬 여부 확인
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next
        return not rev