一、题目描述

剑指 Offer II 027. 回文链表

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：

输入: head = [1,2,3,3,2,1]

输出: true

示例 2：

输入: head = [1,2]

输出: false

提示：

链表 L 的长度范围为 [1, 105]

0 <= node.val <= 9

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

二、解题

2.1题目分析

该题有三种常见解法，分别是递归、拷贝到数组再判断回文、反转后半部分链表。下面是采用后面两种方法解题。

2.2反转后半部分链表

由于回文是前后对称，故只需要反转链表后半部分内容，再与前面进行比较即可。

找到链表后半部分源码如下：

while (fast != nullptr) // 快慢指针，找到后半部分
{
	if (fast->next == nullptr)
		break;
	fast = fast->next->next;
	slow = slow->next;
}
fast = reverseList(slow->next); // 反转后半部分链表
slow = head;

反转链表源码如下：

ListNode* reverseList(ListNode* head)
{
	ListNode* pre = nullptr, * cur = head, * next = nullptr;
	while (cur != nullptr) // 链表正常遍历
	{
		next = cur->next; // 暂存下一个节点
		cur->next = pre; // 下个节点指向前面节点
		pre = cur; // 前面节点指向当前节点
		cur = next; // 继续循环遍历下一个节点
	}
	return pre; // 返回反转后的头结点
}

链表前面和后半部分依次比较源码如下：

while (fast != nullptr) // 比较前半部分和后半部分节点内容
{
	if (slow->val != fast->val) // 前后节点不同不是回文
		return false;
	fast = fast->next;
	slow = slow->next;
}
return true;

2.3完整代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
// 解题思路：先反转链表，然后依次遍历两个链表是否相等
// 思路2：快慢指针找到中间节点，反转后半部分链表，依次比较   
    ListNode* reverseList(ListNode* head)
    {
	    ListNode* pre = nullptr, * cur = head, * next = nullptr;
	    while (cur != nullptr) // 链表正常遍历
	    {
		    next = cur->next; // 暂存下一个节点
		    cur->next = pre; // 下个节点指向前面节点
		    pre = cur; // 前面节点指向当前节点
		    cur = next; // 继续循环遍历下一个节点
	    }
	    return pre; // 返回反转后的头结点
    }

    bool isPalindrome(ListNode* head) {
        if(head->next == nullptr) // 只有一个节点直接返回true
        {
            return true;
        }
        ListNode *fast=head->next, *slow=head; // 注意初始赋值
        while(fast != nullptr) // 快慢指针，找到后半部分
        {
            if(fast->next == nullptr)
                break;
            fast = fast->next->next;
            slow = slow->next;
        }
        fast = reverseList(slow->next); // 反转后半部分链表
        slow = head; 
        while(fast != nullptr) // 比较前半部分和后半部分节点内容
        {
            if(slow->val != fast->val) // 前后节点不同不是回文
                return false;
            fast = fast->next;
            slow = slow->next;
        }
        return true;
    }
};

输出结果

另一种比较低效的解法：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
// 解题思路：先反转链表，然后依次遍历两个链表是否相等
// 思路2：快慢指针找到中间节点，反转后半部分链表，依次比较
    bool isPalindrome(ListNode* head) {
        ListNode *cur=head, *tmpHead=nullptr, *temEnd=nullptr, *tmpCur=nullptr;
        while(cur != nullptr) // 遍历链表
        {            
            tmpCur = tmpHead;
            tmpHead = new ListNode(cur->val); // 创建新节点
            tmpHead->next = tmpCur; // 新节点的next指针指向头结点
            cur = cur->next;
        }
        cur=head;
        tmpCur=tmpHead;
        while(cur != nullptr && tmpCur != nullptr) // 遍历链表
        {            
            if(cur->val != tmpCur->val)
                return false;
            cur = cur->next;
            tmpCur = tmpCur->next;
        }
        ListNode *tmp= nullptr;
        tmpCur=tmpHead;
        while(tmpCur != nullptr)
        {
            tmp = tmpCur;
            tmpCur = tmpCur->next;
            delete tmp;            
        }
        return true;
    }
};

输出结果