234. Palindrome Linked List

Problem Statement

link: LeetCode.cn LeetCode Given the head of a singly linked list, return true if it is a palindrome or false otherwise. Example:

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

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 Approach

The solution involves finding the middle of the linked list, reversing the second half, and then comparing it with the first half to check if the list is a palindrome.

Algorithm

1. Find the Middle: Use the slow and fast pointer technique to find the middle of the linked list.
2. Reverse the Second Half: Reverse the second half of the linked list starting from the middle.
3. Compare Halves: Compare the first half and the reversed second half of the list to determine if they are identical, confirming if the linked list is a palindrome.

Implement

    # 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 head is None:
            return True
        p1 = head
        temp = self.findHalf(head)
        p2 = self.reverse(temp)
        while p2:
            if p1.val != p2.val:
                return False
            p1 = p1.next
            p2 = p2.next
        return True
        
    def findHalf(self, head): 
        p1 = p2 = head
        while p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next
        return p1 if not p2 else p1.next
    
    def reverse(self, head):
        dummyHead = None
        current = head
        while current:
            temp = current.next
            current.next = dummyHead
            dummyHead = current
            current = temp
        return dummyHead

    
    

Twitter  facebook  Email