[234] Palindrome Linked List

判斷linked list 是不是回文
這個我覺得學生時代我應該會QQ
現在完全不會XDDDD 看了別人寫法萬般看不懂～～～
一個一個印出來看才比較懂了一點QQ
桑心啊XD

雖然不是自己寫的, 純紀錄用.

漂亮解法長這樣, 使用遞迴:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* tmp;
bool check(struct ListNode* p)
{
    if (NULL == p)
        return true;

    bool isPal = check(p->next) & (tmp->val == p->val);
    tmp = tmp->next;
    return isPal;
}

bool isPalindrome(struct ListNode* head) {
    tmp = head;
    return check(head);
}

遞迴的意思是有一個pointer 指著head, 然後另一個會移動的就遞迴下去, 一直往後next 直到null (也就是最後一個node) 此時就可以比較兩個pointer 是不是一樣, 接著

(1) 原本指著head 的的pointer 指向下一個node

(2)已經遞迴到tail 的那個這時可以return回上一層, 也就是tail 的前一個node

在此時又去比較(1)和(2), 一樣的話就表示目前還是回文, 繼續repeat, 一個往後一個往前 (遞迴的那個return 回去就是移回上一個)

如此這邊就可以頭尾夾擊(?) 沿路判斷是不是相等 a.k.a 是不是回文了

比較簡單的是先找到中間mid ,
然後reverse其中一半,
再比看看兩半是不是一樣,
就可以確定是不是回文.