# 234. Palindrome Linked List

###### tags: `linked list` `easy` `leetcode`

## Problem
Given the head of a singly linked list, return true if it is a palindrome.

### Sample Input

Input: head = [1,2,2,1]

### Sample Output

true

<br>

:::spoiler **Optimal Space & Time Complexity**

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

:::

<br>

:::spoiler Hint 1

:::

<br>

:::spoiler Hint 2

:::

<br>

:::spoiler Hint 3

:::

<br>

<hr/>

## Solutions

### Official

<br>

---

### Everyone's

:::spoiler 月 Two pointers

// Time(n) Space(1), n is the length of head
var reverseList = function(head) {
    let result = null;
    while(head){
        const record = head.next;
        head.next = result;
        result = head;
        head = record;
    }
    return result;
};

var isPalindrome = function(head) {
    let slow = head, fast = head;
    let length = 0;
    let currNode = head;
    
    while(fast && fast.next){ // get list length
        fast =  fast.next.next; // half length
        slow = slow.next; // slow 位於 middle
        length++
    }
    
    let list = reverseList(slow); // 拿後半的 reversed list
    
    while(length){
        if(currNode.val !== list.val) return false;
        list = list.next;
        currNode = currNode.next;
        length--
    }
    return true
};

:::

<br>

:::spoiler 東 Two pointers

// Time O(n) | Space O(1) ; where n is the amount of nodes linked to input head
var isPalindrome = function(head) {
    let firstHalfHead = head;
    let secondHalfHead = head;
 
    secondHalfHead = getMidNode(secondHalfHead);
    secondHalfHead = reverseLinkedList(secondHalfHead);
    
    while(secondHalfHead) {
        if(firstHalfHead.val !== secondHalfHead.val) return false;
        firstHalfHead = firstHalfHead.next;
        secondHalfHead = secondHalfHead.next;
    }
    return true;
};

const getMidNode = (head) => {
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next
    }
    return slow;
};

const reverseLinkedList = (head) => {
    if(!head || !head.next) return head;
    let prevNode = null;
    let currNode = head;
    let nextNode;
    while(currNode) {
        nextNode = currNode.next;
        currNode.next = prevNode;
        prevNode = currNode;
        currNode = nextNode;
    }
    return prevNode;
}

:::

<br>

:::spoiler YC dummy

/**
 * time: O(2n) - where n is the number of nodes in the head
 * space: O(1)
 */

var isPalindrome = function(head) {
    const len = getLen(head);
    if(len === 1) return true;
    
    let dummy = new ListNode();
    let half = Math.floor(len / 2); // ** 五個返回二
    
    while(half){ // 拿取前半部的 reversed 
        const next = head.next;
        head.next = dummy;
        dummy = head;
        head = next;
        half--;
    }
    
    if(len % 2) head = head.next; 
    // 解決偶基數的 middle 問題，經過上方迴圈，
    // head 會走到中間，沒有餘數代表 head 處於 reversed 最後一位
        
    while(head){
        if(head.val !== dummy.val){
            return false;
        } 
        head = head.next;
        dummy = dummy.next;
    }
    return true;
    
};


function getLen(list){
    let len = 0;
    let curr = list;
    while(curr){
        len++;
        curr = curr.next;
    }
    return len;
}

:::

<br>

:::spoiler Becky Array

//time: O(n) | space: O(n)
var isPalindrome = function(head) {
    let arr = [];//先把linked list做成array
    while ( head !== null ) {
        arr.push(head.val);
        head = head.next;
    }

    // 用雙指針去跑
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        if (arr[left] !== arr[right]) {
            return false;
        }
        left++;
        right--;
    }

    return true;
};

:::

<br>

:::spoiler Raiy String

var isPalindrome = function(head) {
    // Time O(n) Space O(2n)
    // use string
    let original_str = "";
    let reversed_str = "";
    
    while(head){
        original_str += head.val;
        reversed_str = head.val + reversed_str;
        head = head.next;
    }
    
    return original_str === reversed_str;
};

:::

---

## Supplement / Discussion
Solution
使用 Two pointer 的 Space
https://leetcode.com/problems/palindrome-linked-list/discuss/1137027/JS-Python-Java-C%2B%2B-or-Easy-Floyd's-%2B-Reversal-Solution-w-Explanation