Palindrome Linked List

Nov 06, 2017

第42天。

今天的题目是Palindrome Linked List:

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)的空间复杂度),然后在对比。

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

    ListNode *fast = head;
    ListNode *slow = head;
    ListNode *pre = slow;
    while(fast && fast->next) {
        fast = fast->next->next;
        pre = slow;
        slow = slow->next;
    }
    fast = pre->next;
    pre->next = nullptr;

    fast = revertList(fast);

    while(fast && head) {
        if (fast->val != head->val)
            return false;
        fast = fast->next;
        head = head->next;
    }
    return true;
}
ListNode *revertList(ListNode *head) {
    if(!head || !head->next) return head;
    ListNode *pre = head;
    ListNode *cur = head;
    while(cur) {
        ListNode *t = cur->next;
        cur->next = pre;
        pre = cur;
        cur = t;
    }
    head = head->next;
    return pre;
}

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

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

bool check(ListNode* p) {
    if (NULL == p) return true;
    bool isPal = check(p->next) & (temp->val == p->val);
    temp = temp->next;
    return isPal;
}

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

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

LeetCodeLeetCodeLinkedList

Lowest Common Ancestor of a Binary Tree

Invert Binary Tree

comments powered by Disqus