LeetCode 234. 回文链表

本文给出时间复杂度为O(n)O(n)O(n)空间复杂度为O(1)O(1)O(1)的解法思路。对于这样的情况我们可以使用快慢指针确定链表的中间节点初始时让slowslowslow和fastfastfast均等于headheadhead让slowslowslow每次移动1个节点fastfastfast每次移动2个节点如果链表节点数量为偶数最终结果如下判断指针移动结束的条件是fast.nextnull∣∣fast.next.nextnullfast.next null \quad || \quad fast.next.next nullfast.nextnull∣∣fast.next.nextnull不论链表节点数是奇是偶最后slowslowslow指针都会指向颠倒链表的头节点。为了满足空间复杂度为O(1)O(1)O(1)的任务我们原地调整颠倒链表。下面我们讨论原地翻转链表的算法我们最终的目标是这样的首先让cur.nextprecur.next precur.nextpre再按顺序让precur,curnxt,nxtcur.nextpre cur, cur nxt, nxt cur.nextprecur,curnxt,nxtcur.next重复上面的操作直到进行到下面这一步在按precur,curnxt,nxtcur.nextpre cur, cur nxt, nxt cur.nextprecur,curnxt,nxtcur.next顺序进行赋值的过程中发现问题所以判断是否按顺序赋值的条件就是nxt≠nullnxt \neq nullnxtnull跳出循环后处理边界即可slow.next.nextnxt,slow.nextcurslow.next.next nxt, slow.next curslow.next.nextnxt,slow.nextcur最后按顺序比较两个链表每个节点值是否相同即可。classSolution{// 原地翻转链表的方法privatevoidreverseLinkedList(ListNodepreHead){// pre才是待翻转链表真正的头节点ListNodeprepreHead.next;if(pre.nextnull){// 待翻转的链表只有1个节点直接返回return;}// 当前操作的节点ListNodecurpre.next;ListNodenxtcur.next;// 先做一次操作cur.nextpre;while(nxt!null){precur;curnxt;nxtcur.next;cur.nextpre;}// 处理边界preHead.next.nextnxt;preHead.nextcur;}publicbooleanisPalindrome(ListNodehead){if(head.nextnull){// 链表只有1个节点returntrue;}elseif(head.next.nextnull){// 链表只有2个节点return(head.valhead.next.val);}// 初始化快慢指针ListNodeslowhead,fasthead;// 找到中间节点while(fast.next!nullfast.next.next!null){slowslow.next;fastfast.next.next;}// 翻转链表reverseLinkedList(slow);// 让slow等于翻转后链表的头节点slowslow.next;// 开始比较while(slow!null){if(head.val!slow.val){returnfalse;}headhead.next;slowslow.next;}returntrue;}}