LeetCode初级-回文链表

题目：

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

题目分析：

大概思路：先遍历一遍得到链表的长度，然后把前一半链表反转，最后依次比较前一半链表和后一半链表对应位的值，从而得出是否回文。

正好上一篇刚写了反转链表，这一篇就用到了喔。

• 注意：反转完了后指针 pre 后面自动就断链了，上篇有提到，很方便。
• 另一注意点：反转之后需要判断一下长度奇偶，参照上篇图解也很好理解的。

上篇链接：LeetCode-反转链表

C++代码如下：

/**
 * 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;
        
        ListNode* len = head;
        ListNode* pre = NULL;
        ListNode* cur = head;
        ListNode* pnext = NULL;
        int length = 0;
        while (len) {
            length++;
            len = len ->next;
        }
        // 反转
        for (int i = 0;i < length/2;++i) {
            pnext = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = pnext;
        }
        // 奇数情况
        if ((length % 2) == 1) pnext = pnext -> next;
        // 逐个比较
        while (pre) {
            if (pre -> val != pnext -> val) return false;
            pre = pre -> next;
            pnext = pnext ->next;
        }
        
        return true;
    }
};

速度不错哦~