234_Palindrome Linked List

Question

Given a singly linked list, determine if it is a palindrome.

Example:

linked list1 → 2 → 1 → Ø is a palindrome.

linked list1 → 2 → 3 → Ø is not a palindrome.

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

Solution 1

Convert the linked list to array, check if the array is a palindrome.

Time: $O(n)$ extra space: $O(n)$

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

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return True
        # convert linked list to array
        ret = []
        node = head
        while node:
            ret.append(node.val)
            node = node.next
        return ret == ret[::-1]

Solution 2

1. Get the middle of the linked list using a slow pointer and a fast pointer

2. Reverse the second half of the linked list

3. Check if the first half and second half are identical

Time: $O(n)$ Extra space: $O(1)$

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

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None or head.next == None:
            return True
        # find the middle of the linked list 
        # using a slow pointer and a fast pointer
        slow = head
        fast = head
        while fast.next != None and fast.next.next != None :
            slow = slow.next
            fast = fast.next.next
        slow = slow.next
        # reverse the second half of the linked list
        slow = self.reverseList(slow)
        # check if the first half and second half are identical
        while slow != None:
            if head.val != slow.val:
                return False
            else:
                head = head.next
                slow = slow.next
        return True

    # helper function to reverse a linked list    
    def reverseList(self, next_node):
        """
        :type next_node: ListNode
        :rtype: ListNode
        """
        if not next_node:
            return next_node
        prev_node = None
        while next_node:
            cur_node = next_node
            next_node = next_node.next
            cur_node.next = prev_node
            prev_node = cur_node
        return prev_node