Code & Func

第42天。

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(1)的空间复杂度的话，可以直接用一个栈保存，然后在对比，不过我没有实现这个方法。我的解法是先用快慢指针求链表中点，然后在翻转后面的链表（只需要O(n)的时间复杂度和O(1)的空间复杂度），然后在对比。

1
bool isPalindrome(ListNode* head) {
2
    if (!head || !head->next) return true;
3

4
    ListNode *fast = head;
5
    ListNode *slow = head;
6
    ListNode *pre = slow;
7
    while(fast && fast->next) {
8
        fast = fast->next->next;
9
        pre = slow;
10
        slow = slow->next;
11
    }
12
    fast = pre->next;
13
    pre->next = nullptr;
14

15
    fast = revertList(fast);
22 collapsed lines
16

17
    while(fast && head) {
18
        if (fast->val != head->val)
19
            return false;
20
        fast = fast->next;
21
        head = head->next;
22
    }
23
    return true;
24
}
25
ListNode *revertList(ListNode *head) {
26
    if(!head || !head->next) return head;
27
    ListNode *pre = head;
28
    ListNode *cur = head;
29
    while(cur) {
30
        ListNode *t = cur->next;
31
        cur->next = pre;
32
        pre = cur;
33
        cur = t;
34
    }
35
    head = head->next;
36
    return pre;
37
}

然后是在dicuss中看到的解法，相当有趣的技巧：

1
ListNode* temp;
2
bool isPalindrome(ListNode* head) {
3
    temp = head;
4
    return check(head);
5
}
6

7
bool check(ListNode* p) {
8
    if (NULL == p) return true;
9
    bool isPal = check(p->next) & (temp->val == p->val);
10
    temp = temp->next;
11
    return isPal;
12
}

刚开始看的时候感觉好像是错的，但是仔细想想，这个方法相当美妙，利用函数调用来做栈，首先是递归调用check(p->next),这样的话会一直到最后一个节点才开始比较temp->val == p->val，又因为temp = temp->next始终没有执行到，所以现在temp指向第一个元素，而p指向最后一个元素，判断完后，会执行到temp = temp->next，然后check会返回，返回后p就指向了倒数第二个元素，就这样一直迭代下去。

不过这个方法的空间复杂度是O(n).