문제

https://leetcode.com/problems/palindrome-linked-list/

# Definition for singly-linked list.
class ListNode:
	def __init__(self, val=0, next=None):
		self.val = val
        self.next = next

연결 리스트가 팰린드롬 구조인지 판별하라

Input: head = [1,2,2,1]
Output: true

Input: head = [1,2]
Output: false

풀이

내 풀이

연결 리스트들을 배열에 옮겨닮은 후, 원래 배열과 뒤집은 배열이 같은지 반환
-> O(n), 1868 ms

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        
        a = []

        while(1):
            a.append(head.val)

            if head.next == None:
                break

            head = head.next

        return a[::] == a[::-1]

책 풀이

리스트 변환

-> O(n), 2705 ms
pop(0) 하는 부분에서 값을 꺼내온 다음에 모든 값을 앞으로 시프팅 하기 때문에
시간이 많이 걸렸다 -> Deque를 사용 : 이중 연결 리스트 구조로
양쪽 방향 모두 추출하는데 O(1) 시간만큼 걸림

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        q: List = []

        if not head:
            return True

        node = head

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

        return True

데크를 이용한 최적화

-> O(n), 2705 ms -> 1643 ms로 감소
Deque를 사용 : 이중 연결 리스트 구조로
양쪽 방향 모두 추출하는데 O(1) 시간만큼 걸림

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        q: Deque = collections.deque()

        if not head:
            return True

        node = head
        while node is not None:
            q.append(node.val)
            node = node.next

        while len(q) > 1:
            if q.popleft() != q.pop():
                return False

        return True

런너를 이용한 풀이

-> O(n), 1643 ms -> 1541 ms로 감소
링크드 리스트에서 2개의 러너를 사용
하나는 2칸씩 이동하는 러너, 하나는 하나씩 이동하는 러너
2칸씩 이동하는 러너가 끝에 도착하면 하나씩 이동하는 러너는 링크드 리스트에서 중간 위치가됨.
이 점을 이용해 중간 위치를 알 수 있으므로 중간 이전과 중간 이후의 값 비교 가능

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

파이썬 다중 할당

rev = 1, slow = 2->3이라 가정

rev, rev.next, slow = slow, rev, slow.next

rev=2->3, rev.next=1, slow=3이 되고, rev.next=1이므로
최종적으로 rev=2->1, slow=3이 된다.
다중 할당을 하게 되면 이 같은 작업이 동시에 일어나기 떄문에, 이 모든 작업은 중간과정없이
한 번의 트랜잭션으로 끝나게 된다.
V.S

rev, rev.next = slow, rev
slow = slow.next

rev=2->3, rev.next=1, 따라서 rev=2->1이 되는데 rev=slow,
동일한 참조가 되었으며 rev=2->1이 되었기 떄문에 slow=2->1로 바뀐다.
그래소 slow=1이 된다.