LeetCode 234. Palindrome Linked List - Python

LeetCode 234. Palindrome Linked List - Python

Given a singly linked list, determine if it is a palindrome.

 

Example 1:

Input: 1->2
Output: false

 

Example 2:

Input: 1->2->2->1
Output: true

 

문제 정의: 회문(=거꾸로 읽어도 똑같은 결과가 나오는) 연결 리스트인지 확인하라.

 

풀이

- fast 포인터와 slow 포인터를 설정한다. fast포인터는 slow 포인터보다 2배 빠르다.

- 2배 빠르게 움직이는 fast가 연결리스트 끝(null)에 가면 slow 포인터는 중간 노드에 위치한다.

- slow 포인터가 위치한 중앙에서 나머지 오른 쪽 노드들의 순서를 거꾸로 뒤집는다. 

- 반으로 나눠진 두개의 리스트를 순회하면서 두 리스트가 같은지 확인한다.

- 같으면 True, 다르면 False를 반환한다.

 

Accept된 코드: 

class Solution:
    def isPalindrome(self, head):
        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 = slow.next
            rev = rev.next
        return not rev