[Python] 연결 리스트

연결 리스트 (Linked List)

: 데이터 요소의 선형 집합.
동적으로 새로운 노드를 삽입하거나 삭제하기 간편하다.

🎈 팰린드롬 연결 리스트

1️⃣ 데크

• 양방향 모두 O(1)에 접근 가능하므로 리스트보다 효율적인 코드를 작성할 수 있다! ✨
  리스트: q.pop(0) ⇢ O(n)
  데크: q.popleft() ⇢ O(1)

def isPalindrome(self, head: ListNode) -> bool:
	# 데크 자료형 선언
    q: Deque = collections.deque()

    if not head:
    	return True

    node = head
    while node is not Nonee:
    	q.append(node.val)
        node = node.next
    while len(q) > 1:
    	if q.popleft() != q.pop():
        	return False

    return True

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

빠른 런너가 끝에 다다를 때, 느린 런너를 정확히 중간 지점에 도달한다.
느린 런너는 중간까지 이동하면서 역순으로 연결 리스트 rev를 만들어 나간다.
중간에 도달한 느린 런너가 나머지 경로를 이동할 때, 역순으로 만든 연결 리스트의 값들과 일치하는지 확인해나가면 된다.
연결 리스트의 길이가 홀수일 때는, 느린 런너가 중간에 도달했을 때, 한칸 더 앞으로 이동하여 중앙값을 뛰어 넘어야 한다.

def isPalindrome(self, head: 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
    # or
    # return not slow

출처

⌜파이썬 알고리즘 인터뷰⌟ 8장_연결 리스트