leetcode-LL

234. Palindrome Linked List.py

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    """
    d->1->2->2->1
    
    Optimal solution with O(1) space
        step1: find mid node 
        step2: reverse mid node to the end
        step3: compare the first and second half nodes
        
    """
    def isPalindrome(self, head: ListNode) -> bool:
        nums = []
        cur = head
        while cur:
            nums.append(cur.val)
            cur = cur.next
        
        return nums==nums[::-1]
    
    def isPalindrome(self, head: ListNode) -> bool:
        mid = self.get_middle_node(head)
        reversed_head = self.get_reversed_ll(mid)
        m = head
        n = reversed_head
        while n:
            if n.val != m.val:
                return False
            m = m.next
            n = n.next
        return True
    
    def get_middle_node(self, head):
        s = f = head
        while f and f.next:
            s = s.next
            f = f.next.next
        return s
    
    def get_reversed_ll(self, head):
        d = ListNode(-1)
        d.next = head
        cur = head.next
        head.next = None
        while cur:
            nxt = cur.next
            cur.next = d.next
            d.next = cur
            cur = nxt
        return d.next