[LeetCode][Python3] 234. Palindrome Linked List

Problem :

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

My Solution :

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

from collections import deque

class Solution:

def isPalindrome(self, head):

"""

:type head: ListNode

:rtype: bool

"""

queue = deque()

while head:

queue.append(head.val)

head = head.next

while len(queue) > 1:

if queue.popleft() != queue.pop():

return False

return True

Comment :

우선 메모리 제약을 생각하지 않는다면 가장 쉬운 방법은 2 pass로 처리하는 방법이다. 위 처럼 deque를 이용해도 되고 그냥 list에 넣은 다음 양쪽에서 포인터를 중간으로 옮겨가며 비교해봐도 되겠다.

아래는 추가 메모리 공간(자료구조)을 사용하지 않고 O(n)으로 푸는 방법인데, 중간까지 진행하며 앞부분을 reverse 시켜놓고, 중간부터 나머지 절반과 reverse된 앞 부분을 되돌아가며 비교하는 방법이다.

My Solution2 :

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

def isPalindrome(self, head):

"""

:type head: ListNode

:rtype: bool

"""

slow = fast = head

prev = None

while fast and fast.next:

fast = fast.next.next

prev, slow.next, slow = slow, prev, slow.next

if fast:

slow = slow.next

while slow:

if prev.val != slow.val:

return False

prev, slow = prev.next, slow.next

return True