题目链接链接: 链表的回文结构题目要求解题思路 1把原链表复制一份把复制的链表逆置比较原链表和逆置的复制链表的val代码实现 1publicclassPalindromeList{publicbooleanchkPalindrome(ListNodehead){if(headnull){returntrue;}if(head.nextnull){returntrue;}//复制链表ListNodecopynewListNode(-1);ListNodetailcopy;for(ListNodecurhead;cur!null;curcur.next){ListNodenodenewListNode(cur.val);tail.nextnode;tailtail.next;}copycopy.next;//逆置复制的链表ListNodecurcopy.next;copy.nextnull;while(cur!null){ListNodenextNodecur.next;cur.nextcopy;copycur;curnextNode;}//比较 2 个链表的每个节点的值ListNodecur1head;ListNodecur2copy;while(cur1!nullcur2!null){if(cur1.val!cur2.val){returnfalse;}cur1cur1.next;cur2cur2.next;}returntrue;}}以上方法的空间复杂度是O(N) ,并不是题目要求的O(1),由于牛客的判定并不是非常严格所以通过了本题下面介绍真·通过的解法解题思路 2找到链表的中间节点把后半链表(中间节点之后的节点)给逆置在同一个链表中用 2 个指针分别比较对应的节点的val代码实现 2publicclassPalindromeList{publicbooleanchkPalindrome(ListNodeA){//找到中间节点ListNodeslowA;ListNodefastA;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}//逆置后半链表ListNodecurslow.next;while(cur!null){ListNodecurNextcur.next;cur.nextslow;slowcur;curcurNext;}//比较对应的节点值while(A!slow){if(A.val!slow.val){returnfalse;}//处理节点是偶数的情况if(A.nextslow){returntrue;}AA.next;slowslow.next;}returntrue;}}链表的个数是偶数个的情况当完成后半链表的逆置后第一次A和slow的值的判断A.val slow.val并没有返回false,到A.next和slow.next做进一步判断第二次A和slow的值的判断A.val slow.val并没有返回false,到A.next和slow.next做进一步判断此时判断应该结束但是由于开始的时候没有考虑节点是偶数的问题变成了下图在判断值时候直接A.val ! slow.val返回false原本是true的结果变成false因此在A.val slow.valA.next slow的情况,可以认定是链表是偶数个链表节点的情况直接return true