[LeetCode][Python3] 234. Palindrome Linked List
2018. 10. 4. 02:03 |
프로그래밍/LeetCode
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
'프로그래밍 > LeetCode' 카테고리의 다른 글
[LeetCode][Python3] 538. Convert BST to Greater Tree (0) | 2018.10.07 |
---|---|
[LeetCode][Python3] 438. Find All Anagrams in a String (0) | 2018.10.07 |
[LeetCode][Python3] 437. Path Sum III (0) | 2018.10.07 |
[LeetCode][Python3] 283. Move Zeroes (0) | 2018.10.05 |
[LeetCode][Python3] 226. Invert Binary Tree (0) | 2018.10.03 |
[LeetCode][Python3] 206. Reverse Linked List (0) | 2018.10.01 |
[LeetCode][Python3] 198. House Robber (0) | 2018.10.01 |
[LeetCode][Python3] 169. Majority Element (0) | 2018.10.01 |
최근에 달린 댓글 최근에 달린 댓글