一杯茶，一包烟，一道链表盯一天

。

原题如下：

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

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

审题：



题目的描述挺简洁，但是所需要考虑的点还是挺多。那什么是回文链表？在这里就不多描述，我给出几个例子后再总结一下，如下：




只有一个结点的链表属于回文链表。





奇数

个结点的链表可能属于回文链表。





偶数

个结点的链表也有可能属于回文链表。


如果某个链表按照中间的位置折叠前后两个部分的结点数据元素能够完全重合，这样的链表叫做

回文链表

。

可能给我们的单链表情况：



1.空的单链表；


2.只有一个结点的单链表；


3.有多个结点，但是是奇数个结点；


4.有多个结点，并且是偶数个结点。

解题思路：




关键点是找中间位置

。多个结点时，如果我们找到了链表的中间位置，将

前半部分进行反转

或者将

后半部分进行反转

，再逐个比较似乎就变得可行了。反转链表在往期文章中有讲解，这里就不阐述了，现在来看看后面的两种情况。

当单链表有多个结点，并且是

偶数

个结点时，如下：






当单链表有多个结点，并且是

奇数

个结点时，如下：






如何确定链表的中间位置？



思路一：



用

快慢指针

（快慢指针：快指针走两个结点，慢指针走一个结点），当快指针指向最后一个结点时，慢指针所指的位置就是中间结点的位置。

思路二：



先遍历整个单链表，计算出单链表的结点数。结点数除以2，就可以确定第几个结点是中间结点。

两种思路就对应两种解题方案，如果使用快慢指针即思路一，那么适合对链表的后半部分进行反转。如果使用方案二，那么适合对链表的前半部分进行反转。先来看看大家都更能够理解的反转前半部分。

一.反转前半部分

分析：



利用思路二找出两个链表的中间结点位置，如下红色箭头所指结点：

当链表是

偶数个

结点时，我们需要对箭头所指当前位置结点

及

之前的结点进行反转；当链表是奇数个是，我们需要对箭头所指结点之前的结点进行反转（

不包括箭头所指结点

）。


但在进行反转之前我们需要将它的后半部分结点标识出来，很简单的方法是遍历到后半部分的第一个结点，用一个指针指向该结点，如下，蓝色标记：




后半部分结点的第一个结点都是中间结点的下一个结点。

反转后如下：

偶数个结点时：

奇数个结点时：

对反转后的链表就可以进行比较判断了。

代码设计步骤：



1.先计算出链表的长度；


2.用一个指针标识出后半部分的第一个结点；


3.对前半部分进行反转；


4.对反转后的两段链表进行比较。

代码实现：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==nullptr)return false;//空单链表时
        if(head->next==nullptr)return true;//只有一个结点时
        int num=0;
        ListNode*pTraversal=head;
        while(pTraversal)//第一次遍历，计算出结点总个数
        {
            ++num;
            pTraversal=pTraversal->next;
        }
        ListNode*nextHead=nullptr;//指向后半部分头的头指针
        ListNode*priorHead=nullptr;//指向前半部分头的头指针
        ListNode*temp=head;
        int bi=num/2;
        if(num%2!=0)//奇数个结点时
        {
            for(int i=1;i<bi+2;i++)
            {
                temp=temp->next;
            }
        }
        else//偶数个结点
        {     
            for(int i=1;i<bi+1;i++)
            {
                temp=temp->next;
            }
        }
        nextHead=temp;//将后半部分的头指针指向后半部分的第一个结点
        temp=head;//让temp重新指向链表的第一个结点
        for(int i=1;i<=bi;i++)//对前半部分进行反转，采用头插法
        {
            temp=head->next;
            head->next=priorHead;
            priorHead=head;
            head=temp;
        }
        while(priorHead)//反转之后进行比较
        {
           if(priorHead->val!=nextHead->val)return false;
           priorHead=priorHead->next;
           nextHead=nextHead->next;
        }
       return true;
    }
};

这种实现方式大家更能够理解，只是一些代码细节得注意，容易出错。

二.反转后半部分

分析：



利用思路一（快慢指针）找出两个链表的中间结点位置，如下slow箭头所指结点：




对后半部分进行反转，同时要保留一个指向后半部分的第一个结点的指针，如下：



偶数个结点时：

奇数个结点时：

代码设计步骤：



1.利用快慢指针，找出链表的中间结点；


2.对链表后半部分的链表进行反转；


3.比较前后两段链表。

代码实现：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==nullptr)return false;//空单链表时，也可以为true
        if(head->next==nullptr)return true;//只有一个结点时
       ListNode*fast=head;//快指针
       ListNode*slow=head;//慢指针
       while(fast&&fast->next)//确定中间结点位置
       {
           slow=slow->next;
           fast=fast->next->next;
       }
       ListNode*nextHead=nullptr;//指向后半部分链表的第一个结点,初始化为NULL
       while(slow)//反转后半部分，采用头插法
       {
           ListNode*temp=slow->next;
           slow->next=nextHead;
           nextHead=slow;
           slow=temp;
       }
       while(nextHead)//前半部分与后半部分进行比较
       {
           if(head->val!=nextHead->val)return false;
           head=head->next;
           nextHead=nextHead->next;
       }
       return true;
    }
};

解题的方式多种多样，大家选择自己更好理解的适合自己的就行。

我是“老胡”，感谢阅读！！

❤️ ❤️