leetcode234 回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路：逆置前一半，然后从中心出发开始比较即可。

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for singly-linked list.
     
    
   

    

     

    
    

     

       * public class ListNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * ListNode next;
     
    
   

    

     

    
    

     

       * ListNode(int x) { val = x; }
     
    
   

    

     

    
    

     

       * }
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 public boolean isPalindrome(ListNode head) {
     
    
   

    

     

    
    

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

    

     

    
    

     
 return true;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       ListNode slow = head, fast = head;
     
    
   

    

     

    
    

     

       ListNode pre = head, prepre = null;
     
    
   

    

     

    
    

     
 while(fast != null && fast.next != null) {
     
    
   

    

     

    
    

     

       pre = slow;
     
    
   

    

     

    
    

     

       slow = slow.next;
     
    
   

    

     

    
    

     

       fast = fast.next.next;
     
    
   

    

     

    
    

     

       pre.next = prepre;
     
    
   

    

     

    
    

     

       prepre = pre;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(fast != null) {
     
    
   

    

     

    
    

     

       slow = slow.next;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 while(pre != null && slow != null) {
     
    
   

    

     

    
    

     
 if(pre.val != slow.val) {
     
    
   

    

     

    
    

     
 return false;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       pre = pre.next;
     
    
   

    

     

    
    

     

       slow = slow.next;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return true;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103377337