本文共 2252 字，大约阅读时间需要 7 分钟。
题目：请编写一个函数，检查链表是否为回文。给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。测试样例：{1,2,3,2,1}返回：true{1,2,3,2,3}返回：false
思路：判断回文是字符串中也经常会出现的一个问题，逻辑并不复杂：对于字符串，如果是数字判断回文，可以循环使用取模运算和取余运算来判断是否相同；对于字符，怎么判断？
链表中的值通常都是数字，因此对于这样的链表判断回文类似于对数字判断是否是回文。
方法一：时间复杂度O(N),空间复杂度O(N)—利用栈装载N个结点
先遍历一遍链表12321，将结点分别装入栈中，然后再次遍历链表12321同时从栈中弹出结点12321，由于栈起到反向的作用，因此如果两者相同说明是回文结构，这里无论结点是奇数还是偶数都没有关系。只是栈中装入N个结点需要额外占用空间复杂度O(N)。
方法二：时间复杂度O(N),空间复杂度O(N/2)—利用栈装载N/2个结点
也是使用栈，使用两个指针pfast,pslow对链表1234567进行遍历，在遍历同时将pslow遍历的结点放入到栈中321，当pfast遍历结束时，pslow刚好到达中间，于是链表的前面一半已经放入到栈中，刚好是前面一半的逆序321，之后慢指针pslow继续遍历，同时从栈中弹出结点进行比较，相当于将链表的前面一半折过来与后面的一半链表进行比较。
就是对于链表是基数还是偶数的操作有一些区别：
如果是基数，即pfast.next==null时第一遍遍历结束，此时pslow在正中间4结点，此时不要将这个结点放入到栈中，之后分别弹栈和遍历pslow进行比较。
方法三：时间复杂度O(N),空间复杂度O(1),对后面半条逆序,之后两个指针分别从头尾遍历
先找到中间结点，即通过pslow和pfast进行遍历，当pfast.next==null(奇)或者pfast.next.next==null(偶)即说明pfast到达尾部，此时pslow到达中部，将此时的中间结点单独记录pmiddle,同时记录开始的头结点pHead，然后使用指针pmiddle开始对后面的链表进行逆序(逆序保留三个结点即可)
然后从头结点p1和尾部结点开始进行遍历，逐个比较值，直到p1==pmiddle为止。
这里关键是对奇数和偶数情况下的不同处理会带来麻烦。
代码：
publicclass Palindrome { //判断一个链表是否是回文结构 public boolean isPalindrome(ListNode pHead){ //特殊情况判断,当pHead为null,1个结点，2个结点 if(pHead==null) return false; if(pHead.next==null) return true; if(pHead.next.next==null){ return (pHead.val==pHead.next.val ?true:false); } //①先找到链表的中间结点pmiddle ListNode pslow=pHead; ListNode pfast=pHead; //常识：&&只要第一个条件不满足，后面条件就不再判断，这里恰好当pfast.next==null时就不会比较pfast.next.next从而避免了空指针 while(pfast.next!=null&&pfast.next.next!=null){ pfast=pfast.next.next; pslow=pslow.next; } //此时pslow所在的位置就是中间结点 ListNode pmiddle=pslow; //②对pmiddle之后的链表进行逆序 ListNode ppre=pmiddle; ListNode pcur=ppre.next; ListNode pnext=null; while(pcur!=null){ pnext=pcur.next; pcur.next=ppre; ppre=pcur; pcur=pnext; } //此时完成遍历且ppre就是尾结点 ListNode ptail=ppre; ListNode phead=pHead; //③从头尾同时开始进行遍历比较，由规律可知在奇偶状态下，phead先或者同时到达pmiddle while(phead!=pmiddle){ if(phead.val!=ptail.val) returnfalse; phead=phead.next; ptail=ptail.next; } return true; }}