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

  

   

    

     

    
    

     

      package com.chenyu.zuo.linkedList;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      import com.chenyu.zuo.linkedList.PrintCommonPart.Node;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

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

    

     

    
    

     

       * 例如：  
     
    
   

    

     

    
    

     

       * 1->2->1 true  
     
    
   

    

     

    
    

     

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

    

     

    
    

     

       * 1->2->3 false  
     
    
   

    

     

    
    

     

       *思路：
     
    
   

    

     

    
    

     

       *我们只需要几个变量，额外空间复杂度为0（1），
     
    
   

    

     

    
    

     

       *可以在时间复杂度o(N)内完成所有的过程
     
    
   

    

     

    
    

     

       *改变链表的右半区的结构，使整个右半区反转，最后指向中间节点
     
    
   

    

     

    
    

     

       *比如1->2->3->2->1
     
    
   

    

     

    
    

     

       *变成如下结构
     
    
   

    

     

    
    

     

       *1->2->
     
    
   

    

     

    
    

     

       * 3->null
     
    
   

    

     

    
    

     

       *1->2->
     
    
   

    

     

    
    

     

       *
     
    
   

    

     

    
    

     

       *1->2->3->3->2->1
     
    
   

    

     

    
    

     

       *变成如下结构
     
    
   

    

     

    
    

     

       *1->2-> 3->null
     
    
   

    

     

    
    

     

       *1->2->3->
     
    
   

    

     

    
    

     

       *然后从左边和右边分别移动，如果每移动一步每个节点的值都相等
     
    
   

    

     

    
    

     

       *那么就是回文结构，不然不是
     
    
   

    

     

    
    

     

       *最后结果不管怎么样，我们应该把链表恢复原来的样子
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      public class IsPalindrome3 {
     
    
   

    

     

    
    

     

      	public static  class Node{//内部类
     
    
   

    

     

    
    

     

       public Node next;
     
    
   

    

     

    
    

     

       public int value;
     
    
   

    

     

    
    

     

       public Node(int value){
     
    
   

    

     

    
    

     

       this.value=value;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	public boolean isPalindrome(Node head){
     
    
   

    

     

    
    

     

       if(head==null || head.next == null){
     
    
   

    

     

    
    

     

       r
     
    
  
 

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

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