单链表OJ题:LeetCode--234.回文链表

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

朋友们、伙计们,我们又见面了,今天给大家带来的是LeetCode中234题:回文链表

数据结构  :数据结构专栏

作       者  :stackY、

LeetCode:LeetCode刷题训练营

LeetCode--234.回文链表:https://leetcode.cn/problems/palindrome-linked-list/ 

牛客网 - OR36 - 链表的回文结构:https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

目录

1.题目介绍 

2.实例演示 

3.解题思路 


1.题目介绍 

 LeetCode:

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。

单链表OJ题:LeetCode--234.回文链表

牛客网:

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

单链表OJ题:LeetCode--234.回文链表

 对于时间复杂度和空间复杂度都是有要求的,因此我们在LeetCode上面也进行要求。

2.实例演示 

 单链表OJ题:LeetCode--234.回文链表

3.解题思路 

 链表的回文可以转化为数组的回文,将链表拷贝至一个数组,然后转化成数组的回文然后使用快慢指针就可以解决,但是它的时间复杂度是O(N),空间复杂度就是O(N),就不符合题意,因此我们得换一种思路:先找链表的中间结点(可以参考LeetCode--876.链表的中间结点),然后将后半部分逆置(可以参考LeetCode--206.反转链表)然后再依次比较前半部分和逆置后的后半部分,如果不相等则返回false,若比较完两部分之后都相等则返回true,由于我们改变了原链表,因此在比较完之后需要恢复原链表,再将后半部分逆置就恢复到了原来的链表:

单链表OJ题:LeetCode--234.回文链表

 

LeetCode - 代码演示(C语言实现):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 //找中间结点
struct ListNode* middleNode(struct ListNode* head) {
    //快慢指针
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    //找中间结点
    //如果只有一个结点也直接返回
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

//反转链表
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;

    while (cur)
    {
        //保存头结点的下一个结点
        struct ListNode* next = cur->next;

        //头插
        cur->next = newhead;
        //更新新的头
        newhead = cur;

        //迭代
        cur = next;
    }
    return newhead;
}

bool isPalindrome(struct ListNode* head) {
    //找中间结点
    struct ListNode* mid = middleNode(head);
    //反转
    struct ListNode* newmid = reverseList(mid);
    struct ListNode* cur = head;

    //判断
    while (newmid)
    {
        if (cur->val != newmid->val)
        {
            return false;
        }
        else
        {
            cur = cur->next;
            newmid = newmid->next;
        }
    }
    //恢复原链表
    reverseList(newmid);

    return true;
}

牛客网 - 代码演示(C++实现):

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    //找中间结点
    struct ListNode* middleNode(struct ListNode* head)
    {
        struct ListNode* fast = head;
        struct ListNode* slow = head;

        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    //
    struct ListNode* reverseList(struct ListNode* head)
    {
        struct ListNode* newhead = NULL;
        struct ListNode* cur = head;

        while (cur)
        {
            struct ListNode* next = cur->next;
            cur->next = newhead;
            newhead = cur;

            cur = next;
        }
        return newhead;
    }

    bool chkPalindrome(ListNode* A)
    {
        // write code here
        ListNode* mid = middleNode(A);
        ListNode* newmid = reverseList(mid);

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

    }
};

今天的博客就分享到这里,喜欢的老铁留下你的三连,感谢感谢!我们下期再见!! 文章来源地址https://www.toymoban.com/news/detail-441303.html

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

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

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

相关文章

  • LeetCode 热题 100(四):48. 旋转图像、240. 搜索二维矩阵 II、234. 回文链表

    题目要求:就是一个顺时针的旋转过程。  思路:观察矩阵,得出翻转前第i行的第J个元素  等于  翻转后倒数第i列的第J个元素,举例说明,第1行第2个元素为“2”,翻转后到了 倒数第1列的第2个元素。说白了只需要针对翻转前的第i行和翻转后的倒数第i列 代码: 题目要求

    2024年02月11日
    浏览(36)
  • 【数据结构】反转链表、链表的中间节点、链表的回文结构(单链表OJ题)

    正如标题所说,本文会图文详细解析三道单链表OJ题,分别为:  反转链表 (简单)  链表的中间节点 (简单)  链表的回文结构 (较难) 把他们放在一起讲的原因是:  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说?请往下看: 目录 1. 反转链

    2024年02月13日
    浏览(72)
  • 单链表OJ题:LeetCode--160.相交链表

    朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第160道单链表OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 : 数据结构与算法 个  人  主  页  : stackY、 C 语 言 专 栏 : C语言:从入门到精通  Lee

    2024年02月08日
    浏览(48)
  • 单链表OJ题:LeetCode--141.环形链表

    朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中的第141道单链表OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 :数据结构与算法 个  人  主  页  :stackY、 C 语 言 专 栏 :C语言:从入门到精通 LeetC

    2024年02月08日
    浏览(53)
  • 单链表OJ题:LeetCode--138.复制带随即指针的链表

    朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第138道单链表OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 : 数据结构与算法 个  人  主  页  : stackY、 C 语 言 专 栏 : C语言:从入门到精通  Lee

    2024年02月08日
    浏览(67)
  • 单链表OJ题:LeetCode--142.环形链表Ⅱ(判断第一次入环的节点)

    朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第142道单链表OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!   数据结构与算法专栏 : 数据结构与算法 个  人  主  页  : stackY、 C 语 言 专 栏 : C语言:从入门到精通 Le

    2024年02月08日
    浏览(39)
  • 数据结构:带环单链表基础OJ练习笔记(leetcode142. 环形链表 II)(leetcode三题大串烧)

    目录 一.前言  二.leetcode160. 相交链表  1.问题描述 2.问题分析与求解 三.leetcode141. 环形链表 1.问题描述 2.代码思路  3.证明分析  下一题会用到的重要小结论: 四.leetcode142. 环形链表 II 1.问题描述 2.问题分析与求解 Judgecycle接口: 方法一: 方法二:  单链表和带环单链表

    2023年04月08日
    浏览(40)
  • 复习Day05:链表part01:203.移除链表元素、707.设计链表、206.反转链表、234. 回文链表

    之前的blog链接:https://blog.csdn.net/weixin_43303286/article/details/131700482?spm=1001.2014.3001.5501 我用的方法是在leetcode再过一遍例题,明显会的就复制粘贴,之前没写出来就重写,然后从拓展题目中找题目来写。辅以Labuladong的文章看。然后刷题不用CLion了,使用leetcode自带模拟面试环境。

    2024年02月07日
    浏览(38)
  • 链表专题1—24. 两两交换链表中的节点 234.回文链表 143.重排链表 141.环形链表 142.环形链表II 160.链表相交 C++实现

    迭代法,时间复杂度: O ( n ) O(n) O ( n ) , 空间复杂度: O ( 1 ) O(1) O ( 1 ) 时间复杂度、空间复杂度: O ( n ) O(n) O ( n ) 止位置时,慢指针就在链表中间位置。 同时用pre记录慢指针指向节点的前一个节点,用来分割链表,将链表分为前后均等两部分,如果链表长度是奇数,那么

    2024年02月12日
    浏览(45)
  • 【链表OJ题 6】链表的回文结构

    目录 题目来源: 代码实现: 思路分析: 实现过程: 链表的回文结构_牛客题霸_牛客网 (nowcoder.com) 题目描述: 本题的难点在于时间复杂度为O(n),空间复杂度为O(1)。 因为回文结构是正着读反着读是一样的,因此我们 找到链表的中间结点,然后从中间节点开始逆置到尾结点,

    2024年02月06日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包