链表之判断一个链表是否为回文结构（二）

  

   

    

     

    
    

     

      package com.zuo.linkedlist;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      import java.util.Stack;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      import com.zuo.linkedlist.IsPalindrome1.Node;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * 题目：给定一个头结点，判断该链表是否回文结构
     
    
   

    

     

    
    

     

       * 例如：
     
    
   

    

     

    
    

     

       * 1->2->1 true
     
    
   

    

     

    
    

     

       * 1->2->2->1 true
     
    
   

    

     

    
    

     

       * 1->2->3 false
     
    
   

    

     

    
    

     

       * 思路：我们针对前面进行优化，空间复杂度要减少一半，可以把链表对折，把右边的一半压入stack
     
    
   

    

     

    
    

     

       * 然后把链表的左边和压入的到stack弹出来，就行对比
     
    
   

    

     

    
    

     

       * 比如：1->2->2->1
     
    
   

    

     

    
    

     

       * 右边的数据是2，1
     
    
   

    

     

    
    

     

       * 1->2->3
     
    
   

    

     

    
    

     

       * 右边的数据是3
     
    
   

    

     

    
    

     

       * 
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      public class IsPalindrome2 {
     
    
   

    

     

    
    

     

      	 static class Node{
     
    
   

    

     

    
    

     

       public int val;
     
    
   

    

     

    
    

     

       public Node next;
     
    
   

    

     

    
    

     

       public Node(int val){
     
    
   

    

     

    
    

     

       this.val=val;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      	 }
     
    
   

    

     

    
    

     

      	 public boolean isPalindrome2(Node head){
     
    
   

    

     

    
    

     

      		 if(head==null){
     
    
   

    

     

    
    

     

       return false;
     
    
   

    

     

    
    

     

      		 }
     
    
   

    

     

    
    

     

      		 Stack<Node> stack=new Stack<Node>();
     
    
   

    

     

    
    

     

      		 Node right=head.next;
     
    
   

    

     

    
    

     

      		 Node cur=head;
     
    
   

    

     

    
    

     

      		 while(cur.next!=null && cur.next.next!=null){  //得到右边开始的下标，请记住这个地方是需要先写cur.next！=null 
     
    
   

    

     

    
    

     

       right=right
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/50450103