일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- 프로그래머스
- 30. Substring with Concatenation of All Words
- concurrency
- iterator
- Generator
- Class
- 43. Multiply Strings
- 109. Convert Sorted List to Binary Search Tree
- Convert Sorted List to Binary Search Tree
- 315. Count of Smaller Numbers After Self
- 715. Range Module
- Decorator
- 컴퓨터의 구조
- data science
- Python Code
- Substring with Concatenation of All Words
- Python Implementation
- Regular Expression
- LeetCode
- 밴픽
- attribute
- t1
- Python
- Protocol
- 시바견
- shiba
- DWG
- 운영체제
- 파이썬
- kaggle
Archives
- Today
- Total
Scribbling
LeetCode: 234. Palindrome Linked List 본문
Solution for Q.234 within O(N) time complexity and O(1) memory.
To check whether it's a palindrome, we have to check two elements simultaneously from the head and tail.
But in singly linked list, we have no way to check the elements in reverse order from the tail.
So, the solution is simple. Reverse the second half of the list and compare two lists.
Below is the code.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if not head.next:
return True
fast, slow = head, head
while fast != None and fast.next != None:
fast = fast.next.next
slow = slow.next
cur, prv = slow, None
while cur:
nxt = cur.next
cur.next = prv
prv = cur
cur = nxt
p1 = head
p2 = prv
if fast == None:
while p2:
if p2.val != p1.val:
return False
p1 = p1.next
p2 = p2.next
return True
else:
while p2.next:
if p2.val != p1.val:
return False
p1 = p1.next
p2 = p2.next
return True
'Computer Science > Coding Test' 카테고리의 다른 글
LeetCode: 240. Search a 2D Matrix II (0) | 2021.12.27 |
---|---|
LeetCode: 283. Move Zeroes (0) | 2021.12.25 |
LeetCode: 239. Sliding Window Maximum (0) | 2021.12.23 |
LeetCode: 218. The Skyline Problem (0) | 2021.12.22 |
LeetCode: 206. Reverse Linked List (0) | 2021.12.21 |