234-回文链表

编程我只用CPP

2019 年 05 月 06 日

24 次浏览

暂无评论

2930字数

数据结构和算法

来源：力扣（LeetCode）

链接：234. 回文链表

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

示例 1：

输入：1->2
输出：false

示例 2：

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

进阶：

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

二、题解

2.1 暴力法

算法：

遍历链表并复制一份
同时把复制出来的链表反转
使用2个指针分别遍历两个链表对比每个节点

算法复杂度：

时间复杂度：O(n)，需要遍历两次链表。
空间复杂度：O(n)，需要拷贝一份链表。

2.2 快慢指针

判断是否回文数核心思想是先找到链表的中间节点，然后从中间节点开始往两边对比、或者从两边往中间节点对比，以此判断是否为回文数。

算法：

使用2个指针，快指针每次走一步，慢指针每次走两步。当快指针到链表末尾的时候，慢指针在链表中间。这个时候反转后半部分链表，再使用两个指针从链表两端朝中间遍历即可判断出是不是回文。

图示：

当快指针走到末尾的时候，慢指针刚好走到一半，中间节点就在p1和p1前一个节点之间：

以下是节点个数为奇数时，快慢指针从开始到结束时候的状态，中间节点是p1的前一个节点：

可以看到不管链表个数是奇数还是偶数，中间节点都是在慢指针p1附近。

优化

上面的快慢指针算法的执行步骤：

快指针遍历到末尾（遍历了一半的链表）。
反转慢指针到快指针这一段（遍历了一半的链表）。
从两端往中间遍历（遍历了一半的链表）。

整个时间复杂度是O(n)，虽然是O(n)，但是实际上链表遍历了1.5次。因为要对比整个链表，所以算法的时间复杂度不可能低于O(n)，O(n)最理想的情况就是只遍历一次，因此可以想办法优化掉多余的0.5次遍历。

算法如下：

快慢指针分别遍历链表，遍历的过程中，把慢指针经过的节点反转。
当快指针走到链表末尾的时候，慢指针依旧在链表中间的位置，但是此时，慢指针前面的节点都已经反转了。
分别从满指针前后朝两端遍历，对比每个节点。

该算法把前面的步骤1和2合并成了一个操作，减少了一次遍历操作（需要遍历一半链表节点），最后只要遍历1次链表即可完成判断链表是否回文。

算法要注意区分奇数个节点和偶数个节点。

当链表节点个数是偶数个的时候，快指针在指向NULL时，p1前面的就是链表的前半段，从p1开始就是后半段：

链表节点个数是奇数个的时候，p2不会走到NULL（p2要走2步，没有更多的节点了），此时p1在最中间的节点。p1之前是链表的前半段，p1之后就是链表的后半段：

代码：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *slow = head, *fast = head, *pre = NULL, *next = NULL;
        
        // 注意链表为空的时候也要返回true
        if (head == NULL || head->next == NULL) {
            return true;
        }

        // pre节点用于保存中间节点的前面一个节点
        while (fast && fast->next != NULL) {
            fast = fast->next->next;

            // 反转
            next = slow->next;
            slow->next = pre;
            pre = slow; // 备份节点
            slow = next;
        }

        // 奇数个节点的时候，fast指向最后一个节点，非NULL
        // 此时slow指向中间节点，slow下滑一个节点
        // 此时pre所指向的是前半段链表，slow所指向的是后半段链表
        if (fast != NULL) {
            slow = slow->next;
        }

        while (pre != NULL && slow != NULL) {
            if (pre->val != slow->val) {
                return false;
            }
            pre = pre->next;
            slow = slow->next;
        }

        return pre == NULL && slow == NULL;
    }
};