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

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int length(ListNode* head) {
        ListNode* p = head;
        int len = 0;
        while ( p != NULL ) {
            len += 1;
            p = p->next;
        }
        return len;
    }
    ListNode* findKth(ListNode* head, int k) {
        ListNode *p = head;
        int icount = 1;
        while ( icount != k ) {
            p = p->next;
            icount += 1;
        }
        return p;
    }
    ListNode* reverse(ListNode* head) {
        if ( head == NULL or head->next == NULL ) return head;
        ListNode *p1 = head, *p2 = head->next;
        while ( p2 != NULL ) {
            ListNode* next = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = next;
        }
        head->next = NULL;
        return p1;
    }
    bool isPalindrome(ListNode* head) {
        if ( head == NULL or head->next == NULL ) return true;
        int n = length(head);
        // 4 -> find second, 3 -> find first
        ListNode *tmp = findKth(head, n/2);
        ListNode *half = tmp->next;
        tmp->next = NULL;
        ListNode *tail = reverse(half);
        ListNode *p1 = head, *p2 = tail;
        while ( p1 != NULL and p2 != NULL ) {
            if ( p1->val != p2->val ) return false;
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }
};

Notes
The solution using O(1) space requires a number of basic operations of linked list:

• count the length of a linked list
• find k-th node of an linked list
• reverse a linked list
• And a lot of small details...