Palindrome Linked List

Problem 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?

NOTE: the LinkedList is defined as below (In java code):

Solutions

In this problem, we count the LinkedList length. Then we reverse the second half of the LinkedList, compare with the first half, and finally reverse the second half again.
NOTE: In the implementation, the "middle" is not the actually middle of the linked list. It is one node before the actual middle node. This makes the coding easier and shorter.

class Solution:
    # @param {ListNode} head
    # @return {boolean}
    def isPalindrome(self, head):
        if  head == None: return True
        #-----------------Count the linked list's length-------------
        
        lens = self.length_of(head)
        #------------------------------------------------------------
        if lens == 1 : return True
        
        #reverse the second half
        half = (lens+1)/2
        
        #Find the middle
        middle = head
        i = 1
        while i<half:
            i += 1
            middle = middle.next
            
        self.reverse(middle)
        
        #compare
        current1 = head
        current2 = middle.next
        for i in range(lens/2):
            if current1.val != current2.val: return False
            current1 = current1.next
            current2 = current2.next
        
        #reverse the list back
        self.reverse(middle)
        
        return True
    
    def length_of(self, head):
        lens= 0
        current = head
        while current:
            lens += 1
            current = current.next
        return lens
            
    def reverse(self, head):
        if head is None: return
        #reverse all elements after head, not include head
        current = head.next
        head.next = None
        
        while current != None:
            temp = current.next
            current.next = head.next
            head.next = current
            current = temp

II. Solution without counting LinkedList's length
In this solution, we use 2 points, one runs through 1 element, the other runs through 2 elements at a time.

class Solution:
    # @param {ListNode} head
    # @return {boolean}
    def isPalindrome(self, head):
        
        slow = ListNode(0)
        fast = slow
        slow.next = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        self.reverse(slow)
        
        #compare
        current1 = head
        current2 = slow.next
        while current2:
            if current1.val != current2.val: return False
            current1 = current1.next
            current2 = current2.next
        
        #reverse the list back
        self.reverse(slow)
        
        return True
            
    def reverse(self, head):
        if head is None: return
        #reverse all elements after head, not include head
        current = head.next
        head.next = None
        
        while current != None:
            temp = current.next
            current.next = head.next
            head.next = current
            current = temp