런너(runner) 기법이란??

런너(Runner) 기법

• 런너 기법이란 연결 리스트 순회 시 2개의 포인터를 동시에 사용하는 기법이다. 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다.
• fast runner와 slow runner 간의 step을 2배 차이를 두는 식으로 (ex. fast, slow = 2,1) 지정한 후 fast runner가 리스트의 끝지점에 도착하면 slow는 정확히 리스트의 중간 지점에 도달하게 된다.

 

---

런너 기법을 사용하는 문제

leetcode.com/problems/palindrome-linked-list/submissions/

Palindrome Linked List - LeetCode

 

코드

1) 연결리스트를 데크로 변환하여 데크에 저장된 값들을 비교

# 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: ListNode) -> bool:
        #연결 리스트를 데크로 변환
        q = collections.deque()
        
        if not head:
            return True
        
        cur = head
        while cur is not None:
            q.append(cur.val)
            cur = cur.next
            
        #데크 안의 값들을 비교
        while len(q)>1:
            if q.popleft() != q.pop():
                return False
            
        return True

 

2) 런너 기법 이용

# 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: ListNode) -> bool:
        rev = None 
        slow = fast = head
        
        # runner를 이용하여 역순 연결 리스트 구성
        while fast and fast.next: # fast running (slow runner가 딱 연결 리스트 중간까지 도달하도록 함)
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
        if fast: # 연결리스트가 홀수의 원소를 갖는 경우, 가운데 원소를 palindrome 체크에서 배제하도록 함.
            slow = slow.next
        
        # palindrome 여부 체크
        while rev and slow.val == rev.val:
            rev, slow = rev.next, slow.next
        
        return not rev 

연결리스트의 경우 배열와 달리 중간 위치나 길이를 파악하기 위해선 전체를 다 탐색해야 상대적으로 복잡하고 O(n)의 시간이 소요된다.

런너 기법을 사용하면 전체를 다 탐색하지 않아도 되므로, 연결리스트의 중간 위치에 보다 빠르게 접근할 수 있다.