【leetcode】234. Palindrome Linked List

1. 使用快慢指针找中点的原理是fast和slow两个指针，每次快指针走两步，慢指针走一步，等快指针走完时，慢指针的位置就是中点。如果是偶数个数，正好是一半一半，如果是奇数个数，慢指针正好在中间位置，判断回文的时候不需要比较该位置数据。

注意好好理解快慢指针的算法原理及应用。

2. 每次慢指针走一步，都把值存入栈中，等到达中点时，链表的前半段都存入栈中了，由于栈的后进先出的性质，就可以和后半段链表按照回文对应的顺序比较。

solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next) return true;
        stack<int> prehalf;
        ListNode *fast = head, *slow = head;
        prehalf.push(head->val);
        while(fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            prehalf.push(slow->val);
        }
        if(!fast->next) prehalf.pop();
        while(slow->next)
        {
            slow = slow->next;
            if(slow->val != prehalf.top()) return false;
            prehalf.pop();
        }
        return true;
        
    }
};

View Code

要求使用O(1)的空间，那就是不能使用stack了，那么如何代替stack的作用呢，用stack的目的是为了利用其后进先出的特点，以便倒着取出前半段的元素。那么现在不用stack了，如何倒着取元素呢？可以在找到中点后，将后半段的链表翻转一下，这样就可以按照回文的顺序比较了。

solution:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==NULL || head->next==NULL) return true;
        ListNode *slow=head, *fast=head;
        while((fast->next) && (fast->next->next))
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        //reverse last.
        ListNode *last = slow->next, *pre = head;
        ListNode *reverse = NULL;
        while(last)
        {
            ListNode *tmp = last;
            last = tmp->next;
            tmp->next = reverse;
            reverse = tmp;
        }
        //compare pre and reverse.
        while(reverse)
        {
            if(reverse->val != pre->val) return false;
            pre = pre->next;
            reverse = reverse->next;
        }
        return true;
        
    }
};

View Code

注意这个解决方法在翻转链表的过程中容易出错，一定要熟练掌握链表翻转的操作过程！！！

参考

1. GrandYang;

完