234. Palindrome Linked List

• python3

Palindrome : 회문(거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열)

📎 Problem

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

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

Solution Plan

1. Create three pointers: fast and slow initialized to the head of the list, and prev initialized to None. fast will be used to traverse the list at twice the speed of slow.
2. When the fast pointer stops, the slow pointer will be positioned at the middle of the list.
3. From the slow poisiton, reverse the linked list.
4. Compare the First Half and the Reversed Second Half.
5. Return true or false.

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:

        fast, slow, prev = head, head, None
        
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        
        # prev, slow, prev.next = slow, slow.next, None

        # reverse rest of the list
        while slow:
            next_node = slow.next
            slow.next = prev
            prev = slow
            slow = next_node

        fast, slow = head, prev

        while slow:
            if fast.val!= slow.val: return False
            fast, slow = fast.next, slow.next
        
        return True

Result

• Time Complexity : O(n)
• Space Complexity : O(1)