234md.md

LeetCode 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?

##翻譯 給一個單向的連結陣列，判斷他是不是一個回文連結陣列。

進階：你能使用O(n)的時間與O(1)的空間來處理這個題目嗎?

##思路

1. 不考慮進階題的情況很簡單，走訪連結陣列，使用兩個字串來處理
2. 一個正向字串(str = str + value)，另外一個為反向字串(str = value+str)
3. 最後判斷兩個字串是否相等

##解題

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
	
    var rec = "";	//反向字串
    var seq = "";   //正向字串
    
    while(head != null){
        seq += head.val;
        rec = head.val + rec;
        head = head.next;
    }
    // 反向字串與正向字串相等就是回文陣列
    return seq == rec;
    
};

##進階 因為用了另外一個字串，因此額外空間為O(n)，不符合進階的要求，為了不使用額外的O(n)空間，我們先用快慢指針找出linked list的中點
，找到後從中點之後將linked list反轉再與本來的head前半段比較是否相等，這邊需要一個額外的空間儲存反轉後的linked list。

var isPalindrome = function(head) {
	
    var middle = findMiddle(head);   // 找尋中點
    var rNode = reverseNode(middle); // 從中點反轉
    
    // 比對反轉後的node與head前半段是否相等
    while(rNode != null){
        if(head.val != rNode.val) {
            return false;
        }
        head = head.next;
        rNode = rNode.next;
    }
    return true;
    
    
    
    // 使用快慢指針找出中點
    function findMiddle(node){
        var fast = node;
        var slow = node;
        
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    // 反轉linked list
    function reverseNode(node){
        if(node==null || node.next==null) return node;  
        var prev = null;
        var cur  = node;
        while(cur != null){
            var temp = cur;
            cur = cur.next;   
            temp.next = prev;
            prev = temp;
        }
        return prev;
    }
};