연결 리스트와 런너

연결 리스트

대표적인 선형 자료구조 중 하나.
다양한 추상 자료형 구현의 기반이 된다.
동적으로 새로운 노드 삽입 및 삭제가 용이함.

탐색에는 O(n) 시간 소요
시작, 끝 아이템 추가 및 삭제는 O(1) 소요

런너(Runner)

연결 리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법.
한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 사용 가능

2개의 포인터 (Fast Runner, Slow Runner)
주로 Fast Runner는 두 칸씩, Slow Runner는 한 칸씩 이동
Fast Runner가 마지막에 도달할 때면 Slow Runner는 중간점에 위치하게 됨.

[해결할 수 있는 문제]
leetcode 234번, 회문 찾기

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def isPalindrome(self, head: ListNode):
	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

[출처]
파이썬 알고리즘 인터뷰