力扣234. 回文链表

Problem: 234. 回文链表

题目描述

思路

1.定义指针fast，slow分别指向head，int 类型变量n记录链表的长度；
2.将fast指针移动至$\frac{n}{2}$处；
3.若n为奇数则从fast -> next处反转链表；若为偶数则直接从fast位置翻转链表；
4.当fast不为空时，fast与slow每次向后走一步，若其指向的值不相同则返回false否则返回true

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(1)$

Code

class Solution {
public:
    /**
     * Judge the palindromic linked list
     *
     * @param head The head node of linked list
     * @return bool
     */
    bool isPalindrome(ListNode* head) {
        ListNode* p = head;
        ListNode* fast = head;
        ListNode* slow = head;
        int n = 0;
        while (p != nullptr) {
            n++;
            p = p -> next;
        }
        for (int i = 0; i < n / 2; ++i) {
            fast = fast -> next;
        }
        if (n % 2 == 0) {
            fast = reverse(fast);
        } else {
            fast = reverse(fast -> next);
        }
        while (fast != nullptr) {
            if (fast -> val != slow -> val) {
                return false;
            }
            fast = fast -> next;
            slow = slow -> next;
        }
        return true;
    }

    /**
     * Reverse the single linked list
     *
     * @param head The node to be reversed
     * @return ListNode*
     */
    ListNode* reverse(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* nextP = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = nextP;
        }
        return pre;
    }
};