234.Palindrome Linked List

Tags: [palindrome], [list], [linked_list], [reverse], [reverse_linked_list]

Com: {fb}

Link: https://leetcode.com/problems/palindrome-linked-list/\#/description

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

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

Solution: Reverse Linked List

# 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 or not head.next:
            return True

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

        right_head = slow
        prev.next = None

        right_head = self.reverse_list(right_head)
        p1 = head
        p2 = right_head
        while p1 and p2:
            if p1.val != p2.val:
                return False

            p1 = p1.next
            p2 = p2.next

        return True

    def reverse_list(self, head):
        if not head or not head.next:
            return head

        prev = None
        curr = head
        next = None

        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next

        return prev

Revelation:

• Using slow and fast pointers to find the middle point of the linked list. By using above way to find the middle point, the right part's length is <= left part's length.
• Maintain prev, because we need using prev.next to cut off the linked list at the middle node.
• The 'while condition' must check 'while fast and fast.next' because in the loop, we use fast = fast.next.next. But we don't need check whether slow is empty or not, because fast must be None before the slow pointer.
• If the number of nodes is odd, such as 7, the left part will have 4 nodes, and right part will have 3 nodes, after reversing the right part, we only need to compare the first 3 nodes from left part and right part, we don't need care about the 4th node.

Note:

• Time complexity = O(n), n is the number of nodes of the given list.
• Space complexity = O(1).