234. Palindrome Linked List
Category: /leetcode| Leetcode Link | Linked list template |
Given the head of a singly linked list, return true if it is a palindrome.
Example 1:
Input: head = [1,2,2,1]
Output: true
Example 2:
Input: head = [1,2]
Output: false
Solution:
- Fast/Slow pointers
def isPalindrome(self, head: ListNode) -> bool:
if not head: return True
# now head is not NULL
def end_of_1st_half(head):
""" odd: 1->2->3, return 2
even: 1->2->3->4, return 2 """
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
def reverse_list(head):
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
first_half_end = end_of_1st_half(head)
second_half_start = reverse_list(first_half_end.next)
# compare 2 halves
result = True
pos_1, pos_2 = head, second_half_start
while result and pos_2:
if pos_1.val != pos_2.val:
result = False # don't return here, need to reverse the 2nd half
pos_1, pos_2 = pos_1.next, pos_2.next
first_half_end.next = reverse_list(second_half_start)
return result
Other solutions all have same Time: O(N), but Space is O(N).
- convert to list, then two pointers
def isPalindrome(self, head: ListNode) -> bool:
vals = []
current_node = head
while current_node is not None:
vals.append(current_node.val)
current_node = current_node.next
return vals == vals[::-1]
