# LinkedList Palindrome（回文）
實作一個函數來檢查一個鏈結串列是否是一個回文。
eg. 0->1->2->1->0
[#LeetCode 234](https://leetcode.com/problems/palindrome-linked-list/)


### solution 陣列

var isPalindrome = function (head) {
    // Store all values from the linked list in an array
    let valuesFound = [];
    while (head) {
        valuesFound.push(head.val);
        head = head.next;
    }

    // Check if the list of values are a palindrome
    let left = 0;
    let right = valuesFound.length - 1;
    while (left <= right) {
        if (valuesFound[left] !== valuesFound[right]) {
            return false;
        }
        left++, right--;
    }

    return true;
};

:::warning
Follow up: Could you do it in O(n) time and O(1) space?
:::
### solution+ 遞迴

var isPalindrome = function (head) {
    function isPalindromRecursive(recursiveHead) {
        // Reached the end of the list
        if (recursiveHead == null) {
            return true;
        }

        // Recursively traverse the linked list
        const next = isPalindromRecursive(recursiveHead.next);

        // Check if the current level of the linked list mirrors its mirror point
        const valid = recursiveHead.val === head.val;

        // Move the original linked list inward
        head = head.next;
        return next && valid;
    }
    return isPalindromRecursive(head);
};

### solution+ 迭代
> 將反向過的串列與原始串列進行比較，如果他們是相同的，串列也會是相同的。 -> 只要比較串列的前半部分。

var isPalindrome = function (head) {
    // Pass empty or single-item linked lists
    if (!head || !head.next) return true;

    // Traverse the linked list in order to find the mid-point (slow)
    let slow = head,
        fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Reverse the second half of the linked list
    slow.next = reverseLinkedList(slow.next);
    slow = slow.next;

    // Compare the original linked list with the reversed second half
    while (slow) {
        if (head.val !== slow.val) {
            // If a mismatch is detected, break out
            return false;
        }
        head = head.next;
        slow = slow.next;
    }

    return true;
};

var reverseLinkedList = function (head) {
    let nextNode = null;
    let previousNode = null;
    while (head) {
        nextNode = head.next;
        head.next = previousNode;
        previousNode = head;
        head = nextNode;
    }
    return previousNode;
};

:::info

交換的重點在於將「指向下一個 head.next」改成指向「前一個節點 prev」：

**但是為了實現所有的點，我們需要保存一些原有的資訊。因此操作上對每一個點來說，有三個指針：**

head：向自己
head.next：指向下一個
prev：指向前一個
 
**我們需要將三個指針交換成：**
head：指向自己 → 指向下一個（head.next）
head.next：指向前一個（prev）
prev：指向前一個 → 指向自己（head）
:::

---

## 557. Reverse Words in a String III

![](https://i.imgur.com/AVu0TEK.png)

var reverseWords = function(s) {
let temp = s.split(' ');
temp.forEach((v,i)=>{
temp[i] = v.split('').reverse().join('')
})

return temp.join(' ')
};