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.

view plainprint?

1. class Solution:  
2.     # @param {ListNode} head  
3.     # @return {boolean}  
4.     def isPalindrome(self, head):  
5.         if  head == None: return True  
6.         #-----------------Count the linked list's length-------------  
7.           
8.         lens = self.length_of(head)  
9.         #------------------------------------------------------------  
10.         if lens == 1 : return True  
11.           
12.         #reverse the second half  
13.         half = (lens+1)/2  
14.           
15.         #Find the middle  
16.         middle = head  
17.         i = 1  
18.         while i<half:  
19.             i += 1  
20.             middle = middle.next  
21.               
22.         self.reverse(middle)  
23.           
24.         #compare  
25.         current1 = head  
26.         current2 = middle.next  
27.         for i in range(lens/2):  
28.             if current1.val != current2.val: return False  
29.             current1 = current1.next  
30.             current2 = current2.next  
31.           
32.         #reverse the list back  
33.         self.reverse(middle)  
34.           
35.         return True  
36.       
37.     def length_of(self, head):  
38.         lens= 0  
39.         current = head  
40.         while current:  
41.             lens += 1  
42.             current = current.next  
43.         return lens  
44.               
45.     def reverse(self, head):  
46.         if head is None: return  
47.         #reverse all elements after head, not include head  
48.         current = head.next  
49.         head.next = None  
50.           
51.         while current != None:  
52.             temp = current.next  
53.             current.next = head.next  
54.             head.next = current  
55.             current = temp  

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.

view plainprint?

1. class Solution:  
2.     # @param {ListNode} head  
3.     # @return {boolean}  
4.     def isPalindrome(self, head):  
5.           
6.         slow = ListNode(0)  
7.         fast = slow  
8.         slow.next = head  
9.         while fast and fast.next:  
10.             slow = slow.next  
11.             fast = fast.next.next  
12.           
13.         self.reverse(slow)  
14.           
15.         #compare  
16.         current1 = head  
17.         current2 = slow.next  
18.         while current2:  
19.             if current1.val != current2.val: return False  
20.             current1 = current1.next  
21.             current2 = current2.next  
22.           
23.         #reverse the list back  
24.         self.reverse(slow)  
25.           
26.         return True  
27.               
28.     def reverse(self, head):  
29.         if head is None: return  
30.         #reverse all elements after head, not include head  
31.         current = head.next  
32.         head.next = None  
33.           
34.         while current != None:  
35.             temp = current.next  
36.             current.next = head.next  
37.             head.next = current  
38.             current = temp          

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