Palindrome Linked List

Problem: Palindrome Linked List

We first use two pointers to find first half and second half of the linked list. Then we reverse the second half. At last we scan both half to check whether the original linked list is palindrome.

Code in Python:

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

        slow = fast = head
        while fast.next and fast.next.next:
            slow, fast = slow.next, fast.next.next

        _head, slow.next = slow.next, None

        prev = None
        while _head:
            tmp = _head.next
            _head.next, prev, _head = prev, _head, tmp

        _head = prev
        while _head:
            if _head.val != head.val: return False
            _head, head = _head.next, head.next
        return True