LeetCode_链表的回文结构

✨✨所属专栏：LeetCode刷题专栏✨✨

✨✨作者主页：嶔某✨✨

题目描述：

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

就比如：1->2->3->2->1就是回文链表，1->2->3->1->2不是回文链表。

示例代码：

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
};

 分析：

这里我们得到解法是先找到链表的中间节点，之后将中间节点后面的节点全部逆置。之后再从mid节点和链表头节点开始遍历、判断值是否相同，以mid节点和链表头节点都不为空为循环条件。

 所以这里我们先要写出找中间节点的代码：

以前做过类似的题《快慢指针》。快指针一次走两步，慢指针一次走一步。最终慢指针会停在中间节点处。

 注意：这里while循环的条件不能把fast->next放在前面，要先判断的fast不为空，再判断fast的下一个节点是否为空。否则会导致空指针的解引用。

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast = head, *slow = head;
    while(fast && fast->next) {
        slow = slow->next;
        fast  = fast->next->next;
    }
    return slow;
}

链表逆置代码：

struct ListNode* ReverseList(struct ListNode* head ) {
    struct ListNode* pcur = head;
    struct ListNode* prev = NULL;
    while(pcur)
    {
        struct ListNode* tmp = pcur->next;
        pcur->next = prev;
        prev = pcur;
        pcur = tmp;
    }    
    return prev;
}

 主代码：

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
    struct ListNode* mid = middleNode(A); 
    struct ListNode* rmid = ReverseList(mid);
    while(A && rmid)
    {
        if(A->val != rmid->val)
            return false;
        A = A->next;
        rmid = rmid->next;
    }
    return true;
    }
};

本期博客到这里就结束了，如果有什么错误，欢迎指出，如果对你有帮助，请点个赞，谢谢！