Leetcode.234.Palindrome Linked L

题目

给定一个单向链表，判断链表是否是回文(左右对称) 。

Input: 1->2->2->1
Output: true
Input: 1->2->2->3
Output: false

思路

最简单的是使用栈。
可以将链表的前版本部分倒序，然后和后半部分比较。

bool isPalindrome(ListNode* head) {
    if (head == nullptr) return true;

    ListNode *temp = head;
    int n = 1;
    while(temp->next != nullptr) {
        n++;
        temp = temp->next;
    }

    ListNode *before = nullptr;
    ListNode *root = head;
    ListNode *tmp = root->next;
    for (int i = 0; i < n /2; i++) {
        root->next = before;
        before = root;
        root = tmp;
        tmp = tmp->next;
    }
    ListNode *after = n%2 ? root->next : root;

    for (int i = 0;i < n / 2;i++) {
        if (before->val != after->val) {
            return false;
        } else {
            before = before->next;
            after = after->next;
        }
    }

    return true;
}

总结

链表的倒序方法比较奇妙，有点难理解。

    //链表倒序，时间复杂度O(1)
    ListNode *before = nullptr;
    ListNode *root = head;
    ListNode *tmp = root->next;
    for (int i = 0; i < n /2; i++) {
        root->next = before;
        before = root;
        root = tmp;
        tmp = tmp->next;
    }