[leetcode 234] Palindrome Linked List

심지훈·2021년 5월 20일
0

leetcode

목록 보기
8/21

Palindrome Linked List

나의 논리

파이썬 알고리즘 인터뷰에서 링크드 리스트 관련 문제라길래 링크드 리스트를 적극 활용하나? 아니면 이 자료구조를 써야하나 싶었는데
그건 아니고 링크드 리스트가 어떻게 구현되어있는지에 대한 이해를 전제로 깔고 시작하는 문제이다.

링크드 리스트는 다음 노드에 대한 포인터를 가지고 있고 끝 노드에서는 다음노드가 없기때문에 null 또는 None 값을 가지고 있다.
링크드 리스트에서 탐색은 O(n)시간복잡도를 가지며 다음 노드에 대한 포인터를 탐색해나간다.

이러한 이해를 바탕으로 링크드 리스트를 탐색해나가며 노드에 저장되어있는 값을 파이썬의 리스트형 변수에 저장을 한 후, 팰린드롬(앞 뒤가 똑같은 수열 또는 문자열)인지 아닌지 검사하는 알고리즘을 사용하면 된다.

같은 책에서 팰린드롬 판별 알고리즘 문제를 미리 풀어봤기때문에
나는 노드의 각 값을 문자열로 만든뒤 리스트에 담은 후
문자열로 바꾼뒤 문자열 슬라이싱을 통해 팰린드롬인지 아닌지 검사하였다.

def isPalindrome(self, head: ListNode) -> bool:
        s = []
        node = head
        while node is not None:
            s.append(str(node.val))
            node = node.next
            
        s = ''.join(s)
        
        return s == s[::-1]

책에 나온 로직

나는 문자를 리스트에 담고, 리스트를 문자열로 변경하는 등 수고스러운 과정을 거쳤지만 책에서는 덱 자료구조를 이용하여 직관적으로 문제를 풀었다.

def isPalindrome(self, head: ListNode) -> bool:
        
        from collections import deque
        
        d = deque()
        
        node = head
        
        while node is not None:
            d.append(node.val)
            node = node.next
            
        while len(d) > 1:
            if d.popleft() != d.pop():
                return False
            
        return True

문제와 관련하여 잠깐 메모

파이썬 다중할당
rev =1 , slow = 2->3이라고 할때
rev, rev.next, slow = slow, rev, slow.next

우측에서 좌측으로 넘어갈때 라인이 끝나지 않으면 우측 값들은
갱신되지 않은 값이 유효한거 같음

rev = slow이므로 rev=slow= 2->3
rev는 1이므로 rev 2->3이 2->1로 바뀜
slow는 2->3이므로 slow = slow.next는 3-> x 로 바뀜

다중할당을 하면 모든 과정이 1번의 트랜잭션 내에서 일어남 !!

profile
유연한 개발자

0개의 댓글