#234 Palindrome Linked List

檢查一個linked list是否為palindrome

Concept
若在一般可以random access的array或linked list，
就訂start和end pointer 即可
現在的困難點是singly linked list永遠都要從頭往後找，不能反過來找。
若不限制space complexity，time要在O(n)內，可以用stack。
把讀到的元素一一存進stack，若讀到相同的元素就pop出來。
或者建另一個linked list並把它reverse，
兩個linked list各自從頭走到尾。
但題目多了space complexity -> O(1) 的限制。
是否可以從中間切斷，把後半段reverse?

Pseudo code

use slow, fast pointer
start from head, slow walk 1 node, fast walk 2 nodes once.
when fast reach null, slow is in the middle.
cut the link between slow and slow.next.
reverse(slow)
go through slow and head at the same time,
when node value different, return false.
same until the end, return true.

實作時有出現幾個錯誤：

1. 在最上面的slow fast pointer while迴圈的條件中，少了：&& fast.next != null
2. reverse function: return newHead.next -> 應該是return newHead才對
3. 不需要特地把slow和slow.next切斷，reverse後回傳newHead自然就切斷了

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isPalindrome(ListNode head) {

        ListNode slow = head, fast = head;
        while(fast!=null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        slow = reverse(slow);
        fast = head;

        while(slow!=null){
            if(slow.val!=fast.val)    return false;
            slow=slow.next; fast=fast.next;
        }
        return true;
    }

    ListNode reverse(ListNode node){
        ListNode newHead = null;
        ListNode cur = node;
        while(cur!=null){
            ListNode tmp = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = tmp;
        }
        return newHead;
    }
}