234. Palindrome Linked List

Description:

Given the head of a singly linked list, return true if it is a palindrome.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

'''
[1] using list)

idea::
while traversal from head, push value in list().
by reversing list, check list' value and linked list' value.

code::
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        list_values=[]
        
        cur=head
        while cur:
            list_values.append(cur.val)
            cur=cur.next
            
        list_values.reverse()
        
        cur=head
        for val in list_values:
            if val!=cur.val:
                return False
            cur=cur.next
            
        return True
        
-T/C: O(n) # n==len(linked list), 3-pass(making list, reversing list, check isPalindrome)
-S/C: O(n) # for list()
'''

'''
[2] using 9. palindrome number module)

idea::
while traversal linked list. store values in a integer.
then, we will get a integer.
check the integer is Palindrome or not.

BUT, if head' val==0, then the integer can't store leading-zero. so It is incorrect solution.
'''

'''
[3] reversing half of linked list)

idea::
1. get size of linked list.
2. from last node to half of linked list, reverse it(in-place).
3. while traversal from both side(head, last head), check it is palindrome.

code::
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # get size of linked list
        size=0
        cur=head
        while cur:
            size+=1
            cur=cur.next
        
        # move cur to half of the linked list
        half_size=size//2
        cur=head
        while half_size>0:
            cur=cur.next
            half_size-=1
        
        # revese from cur to last
        prev=None
        next=None
        while cur:
            next=cur.next
            cur.next=prev
            prev=cur
            cur=next
            
        # check it is palindrome
        cur=head
        while prev:
            if prev.val!=cur.val:
                return False
            prev=prev.next
            cur=cur.next
        return True
            
-T/C: O(n) # three-pass(get size, reverse, check it is palindrome)
-S/C: O(1)
'''
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        # get size of linked list
        size=0
        cur=head
        while cur:
            size+=1
            cur=cur.next
        
        # move cur to half of the linked list
        half_size=size//2
        cur=head
        while half_size>0:
            cur=cur.next
            half_size-=1
        
        # revese from cur to last
        prev=None
        next=None
        while cur:
            next=cur.next
            cur.next=prev
            prev=cur
            cur=next
            
        # check it is palindrome
        cur=head
        while prev:
            if prev.val!=cur.val:
                return False
            prev=prev.next
            cur=cur.next
        return True