判断一个链表是否为回文结构

    xiaoxiao2021-03-26  6

    题目:给定一个链表的头结点head,判断该链表是否为回文结构

    例如: 1->2->1 ,true 1->2->2->1, true 1->2->3, false

    使用栈来解决

    最直接的想法应该就是利用栈来解决这个问题了。 判断回文结构的最核心思想: 从左到右读的顺序和从右到左读的顺序是一样的,这实际上暗示了使用栈,因为如果压栈序列和出栈序列是一样的,那么这就肯定是一个回文结构了!

    //此处定义的Node类,应该是在一个Node.java文件中。 //或者是在一个类中作为内部类存在。 public class Node{ public int val; public Node next; public Node(int val){ this.val=val; this.next=next; } } //回文方法 public boolean isPalindrome1(Node head){ Stack<Node> stack=new Stack<Node>(); Node cur=head; while(cur!=null){ stack.push(cur); cur=cur.next; } while(!stack.empty()){ // Node tmp=stack.pop(); if(tmp.val==head.val){ head=head.next; } else{ return false; } } return true; }

    判断一半即可

    还有更好的方法,也是利用栈结构,但是其实我们只需要压入链表的一半到栈中即可。 假设链表的长度为N,如果N是偶数,前N/2的节点称为左半区,后N/2的节点称为右半区;如果N是奇数,除去中间的节点,仍然是前N/2为左半区,后N/2为右半区。 链表:1->2->2->1 , 对应左半区 1,2 右半区:2,1

    核心: 检查右半区压入栈后,从栈顶到栈底的顺序是否和左半区的顺序一样。 将链表右半部分存入栈是通过折叠的方法! 实际上还是利用了快慢指针来找到链表的中间位置!

    public boolean isPalindrome2(Node head){ if(head==null|head.next==null) return true; Node right=head.next; Node cur=head; while(cur.next!=null&&cur.next.next!=null){ right=right.next; cur=cur.next.next; } Stack<Node> stack=new Stack<Node>(); while(right!=null){ stack.push(right); right=right.next; } while(!stack.empty()){ if(stack.pop().val!=head.val) return false; head=head.next; } return true; }

    进阶,不需要栈,且O(N)时间复杂度

    步骤:

    改变链表的右半区的结构,反转整个右半区链表,让它最后指向中间节点。左半区第一个节点记为leftStart,右半区反转后的头节点记为rightStartleftStart和rightStart同时向中间点移动,移动每一步都比较leftStart和rightStart的值,如果都一样则为回文结构否则不是不管true还是false,恢复链表链表恢复之后返回结果。

    核心:利用快慢指针找到中间点,反转链表的基本方法(申请多一个结点暂存)

    public boolean isPalindrome3(Node head){ if(head==null||head.next==null) return true; Node n1=head;//存中间位置 Node n2=head; //找到中间节点 while(n2.next!=null&&n2.next.next!=null){ n1=n1.next; n2=n2.next.next; } n2=n1.next;//右半部分第一个节点 n1.next=null; Node n3; //反转右半区 while(n2!=null){ n3=n2.next; //暂存n2下一个节点 n2.next=n1;//反转 n1=n2;//移动n1 n2=n3;//移动n2 } n3=n2;//n3保存最后一个节点,其实也就是现在的右半区的第一个节点,n3始终是优先考虑作为一个暂存节点 n2=head;//n2存左半区第一个节点 boolean res=true; while(n1!=null&&n2!=null){ if(n1.val!=n2.val) { res=false; break; } n1=n1.next; n2=n2.next; } n1=n3.next;//n1存n3的下一个节点,即原链表中的倒数第二个节点。 n3.next=null;//最后一个节点的下一个应该是null //恢复 while(n1!=null){ n2=n1.next;//暂存 n1.next=n3; n3=n1; n1=n2; } return res; }
    转载请注明原文地址: https://ju.6miu.com/read-600113.html

    最新回复(0)