LinkedList : Palindrome Linked List

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

Palindrome Linked List - LeetCode

 

slow & fast pointers로 리스트 중간을 찾은 후

중간에서 오른쪽 부분을 reverse시킨다.

그리고 양쪽 끝에서부터 하나하나 비교하면 palindrome인지 아닌지 알수있다.

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        prev, slow, fast = None, head, head
        while fast and fast.next:
            prev = slow
            slow, fast = slow.next, fast.next.next
        if fast: # 리스트 길이가 홀수일때
            p, pprev = slow.next, slow
            slow.next = None
            while p:
                nxt = p.next
                p.next = pprev
                pprev = p
                p = nxt
        else: # 리스트 길이가 짝수일때
            prev.next = None
            p, pprev = slow, None
            while p:
                nxt = p.next
                p.next = pprev
                pprev = p
                p = nxt
        left, right = head, pprev
        while left and right and left.val == right.val:
            left = left.next
            right = right.next
        return left == right

 

시간 O(N)

공간 O(1) (함수 인자를 수정하는걸로 논란이 좀 있는데 이 문제는 수정하는걸 의도한거같다. 정 찝찝하면 리스트를 다시 뒤집어놔야ㅣㅈ..)

 

홀짝 나눠서 하다보니 코드가 좀 장황해졌는데 줄일수있을까?

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        prev = None
        while slow:
            slow.next, prev, slow = prev, slow, slow.next
        left, right = head, prev
        while right and left.val == right.val:
            left, right = left.next, right.next
        return right == None

slow&fast 한사이클을 돌고나서

slow.next를 None으로 해버리고 남은 리스트를 뒤집으면

left & right 포인터를 가운데쪽으로 하나씩 전진시킬때 right 포인터가 None이 되는지 안되는지 보고 리스트 절반을 봤는지 안봤는지 알수있다.