LeetCode_链表的回文结构-Toy模板网

这篇具有很好参考价值的文章主要介绍了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节点和链表头节点都不为空为循环条件。

LeetCode_链表的回文结构,LeetCode刷题专栏,leetcode,链表,算法

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

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

注意：这里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;
    }
};

本期博客到这里就结束了，如果有什么错误，欢迎指出，如果对你有帮助，请点个赞，谢谢！文章来源地址https://www.toymoban.com/news/detail-859067.html

到了这里，关于LeetCode_链表的回文结构的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！