leetcode Question: Palindrome Linked List

Palindrome Linked List

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?

Analysis:

In order to satisfy the O(n) time and O(1) space requirements, we have to consider in-place check/modify the linked list.  Look at the definition of palindrome, it is easily to find out for a palindrome, if we reverse the second half of the list, the first half and second half are identical.

OK, this is where we start to solve the problem. How about the complexity?
1. First we need to find the middle pointer of the list. It is pretty easy if you remember the slow and fast pointers (similar idea was used in previous leetcode question like here).

2. If we can do the reversing in-place, the space we need are only several temporary pointers. If you remember the previous questions (here), you can easily reverse the list.

The basic idea is shown here by an simple example:
Original list: 1->2->3->4->5
We can have a header pointer: head->1->2->3->4->5
Each time, move current pointer to the first place (which is after head pointer).
head->2->1->3->4->5
head->3->2->1->4->5
head->4->3->2->1->5
head->5->4->3->2->1
Done

3. The reversing step is of O(n) time, then checking two halves will only take O(n), so the overall time complexity is O(n).

Code(C++):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    
    void reverse_list(ListNode** head_ref){
        ListNode* head = *head_ref;
        ListNode* p = head->next;
        while (p && p->next){
            ListNode* tmp = p->next;
            p->next = p->next->next;
            tmp->next = head->next;
            head->next =tmp;
        }
        *head_ref = head;
    }

    bool isPalindrome(ListNode* head) {
        //Get middle pointer: p1
        ListNode* p1 = new ListNode(0);
        p1->next = head;
        ListNode* p2 = p1;
        while(p2 && p2->next){
            p1 = p1->next;
            p2 = p2->next->next;
        }
        
        //reverse second half list
        reverse_list(&p1);
        
        //check palindrome
        p1 = p1->next;
        p2 = head;
        while (p1){
            if (p1->val != p2->val){
                return false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }
};

Code(Python):

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

class Solution(object):
    
    def reverse(self, head):
        p = head.next
        while p and p.next:
            tmp = p.next
            p.next = p.next.next
            tmp.next = head.next
            head.next = tmp
            
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        
        #get middle pointer
        p1 = ListNode(0)
        p1.next = head
        p2 = p1
        while p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next
        
        # reverse second half of list
        self.reverse(p1)
        
        # check palindrome
        p1 = p1.next
        p2 = head
        while p1:
            if p1.val != p2.val:
                return False
            p1 = p1.next
            p2 = p2.next
        return True