甘肃龙网

  1. 首页 > 生活 > >

判断链表是否是回文链表？回文结构，回文串( 二 )

生活百科链表


//(2)完全可以利用快慢指针，确定一个链表的中点，上中点，// 然后，咱们只需要将后半部分放入栈即可！！！然后逆序弹出对比public static boolean isPalidromePen2(Node head){if (head == null || head.next == null) return true;//找中点slowNode fast = head;Node slow = head;while (fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}//fast走不动了，slow就是中点或者上中点//然后，加入一半入栈Node cur = slow.next;Stack stack = new Stack<>();while (cur != null){stack.push(cur);cur = cur.next;}//然后对比head和stack的逆序while (!stack.isEmpty()){if (head.value != stack.pop().value) return false;head = head.next;}//全部通过，则OKreturn true;}

判断链表是否是回文链表？回文结构，回文串

文章插图
本题面试最优解！o(1)空间复杂度，快慢指针逆序对比，再恢复原链表
好，这才是本题的重点！！
你必须在面试时尽可能地拿出最优解，优化时间复杂度，空间复杂度
我们不用栈
（1）既然快慢指针可以用来锁定中点，则我们就有办法找到前后各自一半
（2）让slow指针指向null，断开前后半段，然后让后面半段，逆序链表，逆序后的后半段头节点为cur
（3）然后让head后cur对比，相等就没事，一旦不相等，非回文！
（4）对比完成，拿到结果，然后需要将后半段逆序恢复，然后接上前半段，返回结果后，咱不可以破坏链表的原始结构 。
偶数长度呢？
比如12321判断完之后，你返回结果前要恢复链表哦
这样的话，咱完全没有耗费任何的额外空间
只不过就是手撕代码烦了点，你要搞清楚这个代码的核心思想，然后写清楚每一个步骤，保证不出错
错了也没事啊，调试找错，训练自己的能力 。
手撕哦！！必须手撕，自己想清楚核心思想，一气呵成，调试出来，别抄别人的东西，你就得自己闭眼也能写出来 。
//我们不用栈//（1）既然快慢指针可以用来锁定中点，则我们就有办法找到前后各自一半//（2）让slow指针指向null，断开前后半段，然后让后面半段，逆序链表，逆序后的后半段头节点为cur//（3）然后让head后cur对比，相等就没事，一旦不相等，非回文！//（4）对比完成，拿到结果，然后需要将后半段逆序恢复，然后接上前半段，返回结果后，咱不可以破坏链表的原始结构 。public static boolean isPalidromeFace(Node head){if (head == null || head.next == null) return true;boolean ans = true;//默认是OK//（1）既然快慢指针可以用来锁定中点，则我们就有办法找到前后各自一半Node fast = head;Node slow = head;while (fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}//（2）让slow指针指向null，断开前后半段，然后让后面半段，逆序链表，逆序后的后半段头节点为curNode head2 = slow.next;//后半段头结点slow.next = null;//断开前后//逆序后半段Node pre = null;Node next = head2.next;while (head2 != null){//逆序代码，标准的，next记录head2下次要去的点，让head2回指pre，然后pre去head2，head2去next//直到head2是null停止next = head2.next;head2.next = pre;//逆序pre = head2;head2 = next;}//（3）然后让head后cur对比，相等就没事，一旦不相等，非回文！//此时，pre就是后半段逆序之后的头节点了，咱们让左半段和右半段对比Node cur = head;//左边头head2 = pre;//为了恢复右半段，还得用head2记住这个头节点哦while (cur != null && pre != null){//只要一个结尾了，就不用继续了if (cur.value != pre.value){ans = false;break;//提前结束对比工作}//没事继续留到cur = cur.next;pre = pre.next;}//（4）对比完成，拿到结果，然后需要将后半段逆序恢复，然后接上前半段，返回结果后，咱不可以破坏链表的原始结构 。//刚刚咱们用head2记住了右半段的头结点，故可以利用它恢复pre = null;next = null;while (head2 != null){//逆序代码，标准的，next记录head2下次要去的点，让head2回指pre，然后pre去head2，head2去next//直到head2是null停止next = head2.next;head2.next = pre;//逆序pre = head2;head2 = next;}//恢复以后，pre是头结点，我们需要把左半段的slow接到pre上，完成整体挂接slow.next = pre;return ans;//返回结果}


上一篇：商业智能中数据挖掘的应用

下一篇：没有了