2016年10月11日星期二

234. Palindrome Linked List

Could you do it in O(n) time and O(1) space?

  public boolean isPalindrome(ListNode head) {  
     if(head == null) return true;  
     ListNode slow = head, fast = head;  
     while(fast.next!=null && fast.next.next != null){  
       slow = slow.next;  
       fast = fast.next.next;  
     }  //这里的slow指向的是前半个list的最后一个点(前半个list的长度可能比后半个大1)
     slow.next = reverse(slow.next);  
     slow = slow.next;  
     while(slow!=null){  
       if(slow.val != head.val) return false;  
       slow = slow.next;  
       head = head.next;  
     }  
     return true;  
   }  

没有评论:

发表评论