Leetcode 234,680 @ Java－CONY的世界

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

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

這題想法主要就是two pointer 去找到midpoint ，然後從那點開始reverse list 後比較

/**
 * 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) return true;
        ListNode fast = head.next, slow = head;
        while(fast != null) {
            fast = (fast.next != null)?fast.next.next:fast.next;
            slow = slow.next;
        }
        slow = reverseList(slow);
        fast = head;
        while(slow != null) {
            if(slow.val != fast.val)    return false;
            else{
                slow = slow.next;
                fast = fast.next;
            }            
        }
        return true;            
    }
    public ListNode reverseList(ListNode root) {
        ListNode prev = null, cur = root;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = prev;               
            prev = cur;
            cur = temp;
        }    
        return prev;
    }
}

680. Valid Palindrome II

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

這題一開始又想太複雜了....一直想說要用stringbuilder 的 reverse 來做

以下是當初錯誤複雜的寫法，太複雜結果時間就超過了

class Solution {
    public boolean validPalindrome(String s) {
        StringBuilder s1 = new StringBuilder(s);
        while((s1.length() > 0) && (s1.charAt(0) == s1.charAt(s1.length()-1))){
            s1 = s1.deleteCharAt(0);
            if(s1.length()>0)    
                s1 = s1.deleteCharAt(s1.length()-1);
        }
        if (s1.length()>2){
            StringBuilder s2 = new StringBuilder(s1.subSequence(1,s1.length()));
            StringBuilder s3 = new StringBuilder(s1.subSequence(0,s1.length()-1));
            if(!((s2.toString()).contentEquals(s2.reverse().toString())) && (!(s3.toString()).contentEquals(s3.reverse().toString())))
                return false;
        }
        return true;
    }
}

其實完全可以用簡單的兩次判斷 palidrome呼叫來做出跳過不合字元的動作.....

class Solution {
    public boolean validPalindrome(String s) {
        if(s.length()<2) return true;
        int start =0, end = s.length()-1;
        while(start < end){
            if(s.charAt(start) == s.charAt(end)){
                start++;
                end--;
            } else
                break;
        }        
        return (start==end)? true: (isPalindrome(s,start+1,end)||isPalindrome(s,start,end-1));
    }
    public boolean isPalindrome(String s, int start, int end){
        while(start < end){
            if(s.charAt(start) == s.charAt(end)){
                start++;
                end--;
            } else
                return false;
        }
        return true;
    }
}