【链表OJ题 6】链表的回文结构

这篇具有很好参考价值的文章主要介绍了【链表OJ题 6】链表的回文结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

题目来源:

代码实现:

思路分析:

实现过程:


题目来源:

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

题目描述:

【链表OJ题 6】链表的回文结构

本题的难点在于时间复杂度为O(n),空间复杂度为O(1)。

代码实现:

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast = head, * slow = head;

    while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
    return slow;
}
struct ListNode* reverse(struct ListNode* head)
{
    struct ListNode* prev = NULL, * cur = head, * next = NULL;

    while (cur)
        {
            //尾插
            next = cur->next;
            cur->next = prev;
            prev = cur;
            //迭代
            cur = next;
        }
    return prev;
}
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
    // write code here
    struct ListNode* mid = middleNode(A);
    struct ListNode* rmid = reverse(mid);

    while (rmid)
        {
            if (rmid->val != A->val)
                return false;
            rmid = rmid->next;
            A = A->next;
        }
    return true;
}
};

思路分析:

因为回文结构是正着读反着读是一样的,因此我们找到链表的中间结点,然后从中间节点开始逆置到尾结点,然后用逆置后的链表与原链表的前半段对比,如果每个结点的 val 都相等,就说明此链表是回文结构。

【链表OJ题 6】链表的回文结构

实现过程:

1.使用快慢指针,初始化都指向原链表的头,慢指针一次走一步,快指针一次走两步,快指针走到空或快指针的 next 走到空时,慢指针指向的就是中间结点。

2.找到中间结点后,从中间结点开始到尾结点进行逆置。

这里讲的不够细致,找中间结点与逆置分别是两篇文章,里面讲的比较细致。

找中间结点:http://t.csdn.cn/z3vm5

逆置链表/反转链表:http://t.csdn.cn/Jt38p

我们分别将这两个功能封装成函数使用。

3.以逆置之后的链表头结点作为循环条件(这里其实不难发现逆置后的链表与原链表的长度相等),遍历整个逆置之后的链表,与原链表的 val 对比,如果存在哪个结点的val 不相等就返回 false,如果遍历完整个逆置后的链表都相等就返回 true。

这样的解法可以实现题目的要求:本题的难点在于时间复杂度为O(n),空间复杂度为O(1)。

【链表OJ题 6】链表的回文结构

【链表OJ题 6】链表的回文结构

如果大牛的您看到有什么问题留言给我,我一定会认真看的,谢谢您。如果您看了觉得有收获,关注 + 点赞支持一下呗。

*** 本篇结束 ***文章来源地址https://www.toymoban.com/news/detail-458316.html

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】链表的回文结构

    单链表的操作算法是笔试面试中较为常见的题目。 本文将着重介绍平时面试中常见的关于链表的应用题目,马上要进行秋招了。希望对你们有帮助 _ 😀 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 给定一个链表的头指针

    2024年02月12日
    浏览(53)
  • 链表的回文结构

    对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针 A ,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。 测试样例: 1-2-2-1 返回:true 题目链接:链表的回文结构_牛客题霸_牛客网 

    2024年02月06日
    浏览(49)
  • 【nowcoder】链表的回文结构

    牛客题目链接 链表的回文结构

    2024年01月24日
    浏览(40)
  • LeetCode_链表的回文结构

    ✨✨所属专栏:LeetCode刷题专栏✨✨ ✨✨作者主页:嶔某✨✨ 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。 就比如:1-2-3

    2024年04月26日
    浏览(39)
  • 链表分割,链表的回文结构等经典例题解析!

    链接: 链表分割_牛客题霸_牛客网 (nowcoder.com) https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8tqId=11004rp=2ru=/activity/ojqru=/ta/cracking-the-coding-interview/question-ranking public class Partition {     public ListNode partition(ListNode pHead, int x) {         ListNode cur = pHead;         ListNode bs =

    2024年02月19日
    浏览(51)
  • 【Leetcode】反转链表 合并链表 相交链表 链表的回文结构

      目录 一.【Leetcode206】反转链表 1.链接 2.题目再现  3.解法A:三指针法 二.【Leetcode21】合并两个有序链表 1.链接 2.题目再现  3.三指针尾插法 三.【Leetcode160】相交链表 1.链接 2.题目再现 3.解法 四.链表的回文结构 1.链接 2.题目再现  3.解法 1.链接 反转链表 2.题目再现  3.解法

    2024年02月02日
    浏览(48)
  • 数据结构——图解链表OJ题目

            学完了单链表之后,我们对其基本结构已经有了一定的了解,接下来我们通过一些题目强化对链表的理解,同时学习一些面试笔试题目的新思路以及加强对数据结构单链表的掌握。  目录 题目一.876. 链表的中间结点 - 力扣(LeetCode) 题目二:21. 合并两个有序链表

    2024年02月04日
    浏览(62)
  • 链表中的倒数第k个结点 合并两个链表 分割链表 链表的回文结构

    🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻推荐专栏: 🍔🍟🌯C语言进阶 🔑个人信条: 🌵知行合一 🍉本篇简介::分析力扣中有关链表的部分题目. 题目来源于:牛客网-题目链接 输入一个链表,输出该链表中倒数第k个结点。 示例: 输入:1,{1,2,3,4,5} 返回值:{5} 创建两个指针: ①

    2024年02月10日
    浏览(40)
  • 【面试必刷TOP101】判断一个链表是否为回文结构 & 链表的奇偶重排

    目录 题目:判断一个链表是否为回文结构_牛客题霸_牛客网 (nowcoder.com) 题目的接口: 解题思路: 代码: 过啦!!! 题目:链表的奇偶重排_牛客题霸_牛客网 (nowcoder.com) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这道题我的思路还是比较清晰的,主要是三步走

    2024年02月07日
    浏览(58)
  • 数据结构:链表基础OJ练习+带头双向循环链表的实现

    目录 一.leetcode剑指 Offer II 027. 回文链表 1.问题描述 2.问题分析与求解 (1) 快慢指针法定位链表的中间节点 (2) 将链表后半部分进行反转 附:递归法反转链表 (3) 双指针法判断链表是否回文 二.带头双向循环链表的实现 1.头文件 2.节点内存申请接口和链表初始化接口 3.链表的打

    2024年02月02日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包