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

  

   

    

     

    
    

     

      package com.zuo.linkedlist;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      import java.util.Stack;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      import com.zuo.linkedlist.Josephuskill2.Node;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

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

    

     

    
    

     

       * 例如：
     
    
   

    

     

    
    

     

       * 1->2->1 true
     
    
   

    

     

    
    

     

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

    

     

    
    

     

       * 1->2->3 false
     
    
   

    

     

    
    

     

       *
     
    
   

    

     

    
    

     

       *思路一：
     
    
   

    

     

    
    

     

       *我们把链表的每个节点压入stack，利用后进先出的特点，然后比较每个节点的值是否相等
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      public class IsPalindrome1 {
     
    
   

    

     

    
    

     

      	 static class Node{
     
    
   

    

     

    
    

     

       public int val;
     
    
   

    

     

    
    

     

       public Node next;
     
    
   

    

     

    
    

     

       public Node(int val){
     
    
   

    

     

    
    

     

       this.val=val;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      	 public boolean isPalindrome1(Node head){
     
    
   

    

     

    
    

     

      		 if(head==null){
     
    
   

    

     

    
    

     

       return false;
     
    
   

    

     

    
    

     

      		 }
     
    
   

    

     

    
    

     

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

    

     

    
    

     

      		 Node cur=head;
     
    
   

    

     

    
    

     

      		 while(cur!=null){//记住这个地方不是cur.next不然最后一个节点没有压入栈
     
    
   

    

     

    
    

     

       stack.push(cur);
     
    
   

    

     

    
    

     

       cur=cur.next;
     
    
   

    

     

    
    

     

      		 }
     
    
   

    

     

    
    

     

      		 while(head.next!=null){
     
    
   

    

     

    
    

     

       if(head.val!=stack.pop().val){
     
    
   

    

     

    
    

     

       return false;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       head=head.next;
     
    
   

    

     

    
    

     

      		 }
     
    
   

    

     

    
    

     

      		 return true;
     
    
   

    

     

    
    

     

      	 }
     
    
   

    

     

    
    

     

      	 public static void main(String[] args) {
     
    
  
 

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

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