题目描述

判断他是否是回文串

算法

把他用y总的方式读出来=-= (进数组)，然后双指针搞一搞就好了

算法1

(数组，双指针) $O(n)$

C++ 代码

const int N = 100010;
int a[N];
class Solution {
public:

    bool isPalindrome(ListNode* head) {
        int i = 0;
        while (head){
            a[i++] = head->val;
            head = head->next;
        }
        cout << i;
        bool flag = true;
        for (int j = 0, k = i - 1 ; j < i; j++, k --)
            if (a[j] != a[k])
                flag = false;

        return flag;
    }
};

可以优化 上面只是人类看起来爽一点
①把flag删了
②换算法。
用Stefan大法：
一边找中间点，一边把前一半reverse翻转一下 == 第二半，True就return True，否则return False

def aojsdi(self, head):
    res = None
    slow = fast = head
    while fast and fast.next:
        fast = fast.next.next # fast traverses faster and moves to the end of the list if the length is odd 奇数时快指针先到链表终点
        res, res.next , slow = slow, res, slow.next #翻转 按顺序slow移动就不会影响到res
    if fast:
        slow = slow.next #快指针到终点后把慢指针移一位，跨过中间点。
    while res and res.val == slow.val: # 比较翻转过的前半链和还未被slow指针走过的后半链
        slow = slow.next
        res = res.next
    return not res #如果相同，则res变为None，（即否定完就是True)。如果不相同，就变成False。

c++ 版的tuple元祖操作：

ListNode* tmp = rev;
rev = slow;
slow = slow -> next;
rev -> next = tmp;

C++ 同py

class Solution {
public:

    bool isPalindrome(ListNode* head) {
        ListNode* rev = NULL;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            ListNode* tmp = slow;
            slow = slow -> next;
            tmp->next = rev;
            rev = tmp;
        }
        if (fast) slow = slow->next;
        while (rev && slow)
        {
            //cout << rev->val << ' ' << slow->val << endl;
            if (rev->val != slow->val) return false;
            slow = slow->next;
            rev = rev->next;
        }
        return true;
    }
};

稍微正规点：

class Solution {
public:

    bool isPalindrome(ListNode* head) {
        ListNode* rev = NULL;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            ListNode* tmp = rev;
            rev = slow;
            slow = slow -> next;
            rev -> next = tmp;
        }
        if (fast) slow = slow->next;
        while (rev && rev->val == slow->val)
        {
            //cout << rev->val << ' ' << slow->val << endl;
            //if (rev->val != slow->val) return false;
            slow = slow->next;
            rev = rev->next;
        }
        return not rev;
    }
};