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;
    }
};