LeetCode 234. 回文链表

本文给出时间复杂度为O(n)O(n)O(n)，空间复杂度为O(1)O(1)O(1)的解法思路。
对于这样的情况

我们可以使用快慢指针确定链表的中间节点，初始时让slowslowslow和fastfastfast均等于headheadhead

让slowslowslow每次移动1个节点，fastfastfast每次移动2个节点

如果链表节点数量为偶数，最终结果如下

判断指针移动结束的条件是
fast.next==null∣∣fast.next.next==nullfast.next == null \quad || \quad fast.next.next == nullfast.next==null∣∣fast.next.next==null
不论链表节点数是奇是偶，最后slowslowslow指针都会指向颠倒链表的头节点。为了满足空间复杂度为O(1)O(1)O(1)的任务，我们原地调整颠倒链表。

下面我们讨论原地翻转链表的算法

我们最终的目标是这样的

首先让cur.next=precur.next = precur.next=pre

再按顺序，让pre=cur,cur=nxt,nxt=cur.nextpre = cur, cur = nxt, nxt = cur.nextpre=cur,cur=nxt,nxt=cur.next

重复上面的操作，直到进行到下面这一步

在按pre=cur,cur=nxt,nxt=cur.nextpre = cur, cur = nxt, nxt = cur.nextpre=cur,cur=nxt,nxt=cur.next顺序进行赋值的过程中，发现问题，所以，判断是否按顺序赋值的条件就是
nxt≠nullnxt \neq nullnxt=null
跳出循环后，处理边界即可
slow.next.next=nxt,slow.next=curslow.next.next = nxt, slow.next = curslow.next.next=nxt,slow.next=cur

最后按顺序比较两个链表每个节点值是否相同即可。

classSolution{// 原地翻转链表的方法privatevoidreverseLinkedList(ListNodepreHead){// pre才是待翻转链表真正的头节点ListNodepre=preHead.next;if(pre.next==null){// 待翻转的链表只有1个节点，直接返回return;}// 当前操作的节点ListNodecur=pre.next;ListNodenxt=cur.next;// 先做一次操作cur.next=pre;while(nxt!=null){pre=cur;cur=nxt;nxt=cur.next;cur.next=pre;}// 处理边界preHead.next.next=nxt;preHead.next=cur;}publicbooleanisPalindrome(ListNodehead){if(head.next==null){// 链表只有1个节点returntrue;}elseif(head.next.next==null){// 链表只有2个节点return(head.val==head.next.val);}// 初始化快慢指针ListNodeslow=head,fast=head;// 找到中间节点while(fast.next!=null&&fast.next.next!=null){slow=slow.next;fast=fast.next.next;}// 翻转链表reverseLinkedList(slow);// 让slow等于翻转后链表的头节点slow=slow.next;// 开始比较while(slow!=null){if(head.val!=slow.val){returnfalse;}head=head.next;slow=slow.next;}returntrue;}}