234. Palindrome Linked List

주어진 linked list가 회문인지 판단하는 문제이다.

난이도는 쉽다. 

 

linked list를 직접 변경할 수 없으니, in-out이 쉬운 구조가 되어야한다. 

python에서는 list에서 특정 지점에서 pop도 지원한다. 

 

1) list 이용하는 방법

    def isPalindrome(self, head: ListNode) -> bool:
        lst = []

        if not head: return True
        
        while head:
            lst.append(head.val)
            head = head.next

        while len(lst)>1:
            if lst.pop(0) != lst.pop():
                return False
        return True

위 방법은 pop할때마다 list를 재배치하기때문에 시간이 더 많이 들 수 밖에 없다. 

그리고 linked list를 한번 순회하면서 다시 배열을 만들어야 한다. 

 

2) dequeue를 이용

 

리스트는 pop을 했을 때, 조정이 필요했지만, dequeue를 사용하면 조절이 불필요하다. 
따라서 리스트보다는 빠르다는 장점이 있다. 

    def isPalindrome(self, head: ListNode) -> bool:
        
        if not head:
            return True
        
        q = collections.deque()

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

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

        return True

 

3) Runner 기법

블로그를 작성하는 목적이랄까...내가 모르는 것을 정리하기 위함이다.

linked list 문제를 풀면서 순환하고, value 저장하고 이런것만 했었지, Runner기법을 처음 봤다. 

 

처음에는 신기하고도 했다. two pointer와 비슷한 전략인것 같다. 

 

slow, fast를 head와 동일한 위치에 두고 slow는 한칸씩, fast는 두칸씩 전진하는 기법이다. (linked list에 다음 저장값을 가리키는 next가 있기 때문에 가능한 전략인것 같다.)

 

마지막에 fast가 끝까지 가고 None이 되면, slow는 중앙값에 오게 된다. 

 

그림으로 설명해보면, 

 

1) 처음에는 아래와 같이 slow = fast = head로 같은 위치에 있다. 

2) 이 다음에는 slow는 한칸, fast는 두칸을 전진 시킨다. slow를 전진시키면서 값을 역순으로 저장시킨다. 

최초 None 이었던 값의 앞에 현재 slow값을 넣게 된다. 

3) 한번 더 전진시키면 slow가 중앙에 오고, fast는 끝 지점에 간다. 

slow를 움직이면서 역순으로 저장시킨 값과 현재 slow부터 끝 값까지 하나씩 비교해가면 회문인지 아닌지 판단할 수 있다는 것이다. 

 

참 신기하다 이런 방법이 있는줄도 몰랐는데, 이번에 책보고 공부하면서 찾아보니 linked list에서는 많이 사용되는 방법이라고 한다. 

    def isPalindrome(self, head: ListNode) -> bool:
        slow = fast = head
        rev = None
        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