【刷题记录】链表的回文结构

简介: 【刷题记录】链表的回文结构

本系列博客为个人刷题思路分享,有需要借鉴即可。

1.题目链接:

LINK

2.详解思路:

思路:思路:先找到中间节点,然后逆置后半部分链表,一个指针指向链表的头节点,再一个指针指向逆置的头节点,一一进行比对。

本身这个题目时比较难的,所以先搞几个简单的相关题目铺垫一下

铺垫题目1:若需要见详解请单击:LINK

铺垫题目2:若需见详解,请单击:LINK

所以解决回文链表这道题要结合上面两道题目的代码:先找到中间节点再逆置,再比对。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//找到中间结点
struct ListNode* middleNode(struct ListNode* head) {
    //思路2:快慢指针法
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next)//快指针走到头
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
    //逆置链表为空
    if(head == nullptr) 
    return head;
    //不为空
    struct ListNode* n1 = nullptr;
    struct ListNode* n2 = head;
    struct ListNode* n3 = head->next;
    while(n2)
    {
        //逆置
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)//n3不为空
        {
            n3 = n3->next;
        }
    }
    return n1;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        //找到中间节点
        struct ListNode* pMidNode = middleNode(A);
        //逆置中间节点及其以后的节点
        struct ListNode* pNewMidNode = reverseList(pMidNode);
        //对比
        while(A&&pNewMidNode)
        {
            if(pNewMidNode->val!=A->val)
            {
                return false;
            }
            //向后走
            A = A->next;
            pNewMidNode = pNewMidNode->next;
        }
        return true;
    }
};

完。


相关文章
|
2月前
|
程序员
【刷题记录】移除链表元素
【刷题记录】移除链表元素
|
2月前
|
索引 Python
【Leetcode刷题Python】328. 奇偶链表
在不使用额外空间的情况下,将链表中的奇数和偶数索引节点重新排序的方法,并提供了相应的Python实现代码。
30 0
|
2月前
|
Python
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现,通过先序遍历二叉树并调整节点的左右指针,将二叉树转换为先序遍历顺序的单链表。
23 3
【Leetcode刷题Python】114. 二叉树展开为链表
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
42 5
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
33 4
|
2月前
|
存储 Python
【Leetcode刷题Python】23. 合并K个升序链表
合并K个升序链表的方法:使用数组排序的暴力求解法、使用小顶堆的高效方法,以及分而治之的策略,并提供了相应的Python实现代码。
16 1
|
2月前
|
存储 Java 开发者
揭秘!HashMap底层结构大起底:从数组到链表,再到红黑树,Java性能优化的秘密武器!
【8月更文挑战第24天】HashMap是Java集合框架中的核心组件,以其高效的键值对存储和快速访问能力广受开发者欢迎。在JDK 1.8及以后版本中,HashMap采用了数组+链表+红黑树的混合结构,实现了高性能的同时解决了哈希冲突问题。数组作为基石确保了快速定位;链表则用于处理哈希冲突;而当链表长度达到一定阈值时,通过转换为红黑树进一步提升性能。此外,HashMap还具备动态扩容机制,当负载因子超过预设值时自动扩大容量并重新哈希,确保整体性能。通过对HashMap底层结构的深入了解,我们可以更好地利用其优势解决实际开发中的问题。
64 0
|
2月前
|
机器学习/深度学习
【刷题记录】相交链表
【刷题记录】相交链表
|
2月前
【刷题记录】链表的中间结点
【刷题记录】链表的中间结点
|
4月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表