Skip to main content

Palindrome Linked List

Question​

None

Example 1
Input: 1->2->3->2->1
Output: True

Solution​

all//Palindrome Linked List.py


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

class Solution:
    def isPalindrome(self, head):
        # check for empty list
        if head is None:
            return True

        # get the middle of the linked list
        slow_ptr = head
        fast_ptr = head
        while fast_ptr.next != None and fast_ptr.next.next != None:
            slow_ptr = slow_ptr.next
            fast_ptr = fast_ptr.next.next

        # reverse the second half of the linked list
        ptr1 = slow_ptr
        ptr2 = slow_ptr.next
        while ptr2 != None:
            temp = ptr2.next
            ptr2.next = ptr1
            ptr1 = ptr2
            ptr2 = temp

        # compare the first and second half of the linked list
        ptr3 = head
        ptr4 = ptr1
        while ptr3 != None and ptr4 != None:
            if ptr3.val != ptr4.val:
                return False
            ptr3 = ptr3.next
            ptr4 = ptr4.next

        return True