C++速通LeetCode第5题-回文链表

 解法1，堆栈O(n)简单法：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> s;
        ListNode* cp = head;
        bool flag = true;
        while(cp!=nullptr)
        {
            s.push(cp->val);
            cp = cp->next;
        }
        while(head!=nullptr)
        {
            if(s.top()!=head->val)
            {
                return false;
            }
            else
            {
                s.pop();
                head = head->next;
            }
        }
        return true;
    }
};

解法2， 快慢指针确定中间节点并向后逆序O(1):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    //找到开始逆序的中间节点slow
    ListNode* MiddleNode(ListNode* ori)
    {
        ListNode* countTest = ori;
        ListNode* middleStart = nullptr;
        while(countTest!=nullptr)
        {
            countTest = countTest->next;
        }
        ListNode* fast = ori;
        ListNode* slow = ori;
        
        //奇数偶数一样
        while(fast != nullptr && fast->next!= nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        middleStart = slow;
        return middleStart;
    }

    //从slow的中间节点开始逆序,返回逆序后半序列的头节点
    ListNode* ReverseNode(ListNode* start)
    {
        ListNode* pre = nullptr;
        ListNode* cur = start;

        while(cur != nullptr)
        {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    bool isPalindrome(ListNode* head) {
        ListNode* rev = ReverseNode(MiddleNode(head));
        while(rev!=nullptr)
        {
            if(rev->val!=head->val)
            {
                return false;
            }
            else
            {
            head = head->next;
            rev = rev->next;
            }
        }
        return true;
    }
};