题解 | #判断一个链表是否为回文结构#

判断一个链表是否为回文结构

https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f

1.采用双指针

2.确认是奇数链表还是偶数链表

3.翻转慢指针后面的链表，注意不包含当前指针

4.区分奇偶链表的方式就是fast->next为空指针的话，那么是奇数链表，若是fast-》next->next为空指针的话那么久就是偶数链表

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    ListNode* reverseList(ListNode* listNode)
    {
        if(listNode == nullptr) return nullptr;
        ListNode* newList;
        ListNode* cur = listNode;
        ListNode* temp;
        while(cur != nullptr)
        {
            ListNode* next = cur->next;
            cur->next = temp;
            temp = cur;
            cur = next;
        }
        return temp;
    }
    bool isPail(ListNode* head) {
        // write code here
        //找中间节点，然后不断
        //原地翻转一直都中间节点
        if(head == nullptr) return true;
        if(head->next == nullptr) return true;
        if(head->next == head->next->next && head->next->next->next == nullptr) return true;
        if(head->next != head->next->next && head->next->next->next == nullptr) return false;
        
        //如何区分奇偶，就是快指针下一个为nullptr，要么是
        ListNode* fastPtr = head;
        ListNode* slowPtr = head;
        ListNode* temp = nullptr;
        ListNode* cur = head;
        while(fastPtr ->next != nullptr && fastPtr->next->next != nullptr)
        {
            fastPtr = fastPtr->next->next;
            //翻转链表            
            slowPtr = slowPtr->next;    
        }
        
        //奇数链表
        if(fastPtr->next == nullptr)
        {
            ListNode* newList = reverseList(slowPtr->next);
            while(cur != slowPtr)
            {
                if(cur->val != newList->val)
                {
                    return false;
                }
                cur = cur->next;
                newList = newList->next;
            }
        }
        else if(fastPtr->next != nullptr)
        {
            //还是为了因为fastPtr还在用，所以不能在if之前调用
            ListNode* newList = reverseList(slowPtr->next);
            while(cur != slowPtr->next)
            {
                if(cur->val != newList->val)
                {
                    return false;
                }
                cur = cur->next;
                newList = newList->next;
            }
        }
        return true;
    }
};