详解链表oJ<反转链表,链表的中间节点及链表的回文>

这篇具有很好参考价值的文章主要介绍了详解链表oJ<反转链表,链表的中间节点及链表的回文>。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

详解链表oJ<反转链表,链表的中间节点及链表的回文>,链表,数据结构

hello,大家好,这里是Dark FlameMaster,今天和大家分享的是有关数据结构链表的几道题目,链表的中间节点,反转链表及判断链表是否为回文结构,放在一起讲解会印象更加深刻。

一,链表的中间节点

  1. 链接:链表的中间节点

详解链表oJ<反转链表,链表的中间节点及链表的回文>,链表,数据结构

详解链表oJ<反转链表,链表的中间节点及链表的回文>,链表,数据结构

分析:
 如果想要得到链表的中间节点,最简单的思路就是从头结点遍历整个链表,就可以知道链表的长度,假设为num个,要求是如果为偶数个数,返回第二个节点。得到个数后要创建新的节点,往后走num/2个位置。如果num为奇数,如5,往后next两步,如果是偶数如6,往后next3步,皆满足要求。
实现:

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* ret = head;
    int len = 0;
    int k = 0;
    while(ret)
    {
        ret = ret -> next;
        len++;
    }
    ret = head;
    while(k < len / 2)
    {
        k++;
        ret = ret -> next;
    }
    return ret;
}

此题还有一种双指针的方法
思路:
 设置快慢指针,快指针一次走两步,慢指针一次走一步,还是分偶数和奇数的情况。
如果是奇数的话
详解链表oJ<反转链表,链表的中间节点及链表的回文>,链表,数据结构
如果是偶数的话
详解链表oJ<反转链表,链表的中间节点及链表的回文>,链表,数据结构
要注意观察fast的最终位置
实现如下

struct ListNode* middleNode(struct ListNode* head) {
	struct ListNode* val = NULL;
	struct ListNode* baga = NULL;
	val = head;
	baga = head;
	while (val->next != NULL && val->next->next != NULL)
	{
		val = val->next->next;
		baga = baga->next;
	}
	if (val->next == NULL)
	{
		return baga;
	}
	else
	{
		return baga->next;
	}
}

二,反转链表

链接:反转链表

这道题的介绍很简单,给定一个链表head,将链表反转过来。就像这样。
详解链表oJ<反转链表,链表的中间节点及链表的回文>,链表,数据结构

详解链表oJ<反转链表,链表的中间节点及链表的回文>,链表,数据结构
需要注意的是,这个链表的长度有可能为零。
思路:
 解决这道题,不可冒昧更改一个节点的指向,要记录后续节点,同时还要保留前一个节点,好让这个节点可以指向前一节点,所以要设置三个结构体指针变量,分别表示要修改的节点,要修改节点的前一节点,该节点的后边的节点。
实现

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode*n1,*n2,*n3;
    n1=NULL;//设置n1为空
    n2=head;//n2为head,首先指向空
    if(n2)
    {
        n3=n2->next;//判断n2是否为空,若为空则没有next      
    }
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)//判断n3是否为空
        {
            n3=n3->next;
        }
    }
    return n1;
}

下边的动图可以帮助大家理解
详解链表oJ<反转链表,链表的中间节点及链表的回文>,链表,数据结构
对比代码看完这些动图就可以很清晰的理解。

三,链表的回文

链接:链表的回文
详解链表oJ<反转链表,链表的中间节点及链表的回文>,链表,数据结构
设计时间复杂度为O(N),空间复杂度为O(1)的算法

时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

 空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
 上边已经说了链表的长度有限制,空间复杂度为O(1)无疑,只要写出的代码中不使用两层以上循环遍历,用有限的多个循环,时间复杂度都为O(1)
判断是否为回文结构
如用例中的1-2-2-1,从中间分割后两边对称。
再如
1-2-3-2-1,仍然为回文结构。

如何判断是否为回文结构呢?好像很难,因为不是双向链表,我们比较的时候找不到尾的前一个,如果硬要一个一个判断的话,时间复杂度一定不符合要求。

如果使用上边的两个题目的思路
 上边的找中间节点,刚好为后一个中间节点,找到中间节点后,记录中间节点后,将中间结点之后的链表反转,反转后就可以进行比较了。这也是这三道题放在一起的原因。直接cv,将函数复制过来,判断函数内容十分简单,大家可以对照观察。
思路已经十分清楚了
实现如下:

class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head) {
	struct ListNode* val = NULL;
	struct ListNode* baga = NULL;
	val = head;
	baga = head;
	while (val->next != NULL && val->next->next != NULL)
	{
		val = val->next->next;
		baga = baga->next;
	}
	if (val->next == NULL)
	{
		return baga;
	}
	else
	{
		return baga->next;
	}
}
struct ListNode* reverseList(struct ListNode* head){
    struct ListNode*n1,*n2,*n3;
    n1=NULL;
    n2=head;
    
    if(n2)
    {
        n3=n2->next;
        
    }
        while(n2)
         {
             n2->next=n1;
            n1=n2;
            n2=n3;
             if(n3)//判断n3是否为空
              n3=n3->next;
         }
    return n1;
}

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

    }
};

鄙人才疏学浅,如果有更好的方法欢迎评论区留言。
 这三道题讲到这里就结束啦,如果有帮助的话希望大家三连支持哇文章来源地址https://www.toymoban.com/news/detail-715779.html

到了这里,关于详解链表oJ<反转链表,链表的中间节点及链表的回文>的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【链表OJ 3】链表的中间结点

    前言:          本文收录于http://t.csdn.cn/n6UEP数据结构刷题的博客中,首先欢迎大家的来访,其次如有错误,非常欢迎大家的指正!我会及时更正错误! 目录 一.链表的中间结点  1.1原理:快慢指针的使用 链表元素个数为奇数时 链表元素个数为偶数时 1.2循环条件问题? 来源:87

    2024年02月14日
    浏览(50)
  • 【链表OJ】链表中倒数第k个结点 合并两个链表(含哨兵位) 分割链表 链表的回文结构

    前言: 💥🎈个人主页:​​​​​​Dream_Chaser~ 🎈💥 ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣和牛客上链表OJ题目 目录  一、链表中倒数第k个结点 题目描述: 解题思路: 二.合并两个链表(含哨兵位)  题目描述: 解题思路:                                     

    2024年02月12日
    浏览(50)
  • 反转链表、链表的中间结点、合并两个有序链表【LeetCode刷题日志】

    给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 这里解释一下三个指针的作用: n1:记录上一个节点,如果是第一个就指向空 n2:记录此节点的位置 n3:记录下一个节点的位置,让翻转后能找到下一个节点

    2024年02月03日
    浏览(49)
  • 【算法入门&链表】【模板】链表|反转链表|合并排序链表|删除链表的节点

    ✅作者简介:热爱后端语言的大学生,CSDN内容合伙人 ✨精品专栏:C++面向对象 🔥系列专栏:算法百炼成神 本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面

    2024年02月17日
    浏览(60)
  • 【leetcode】链表的中间节点|链表中倒数第k个节点

    目录 1.链表的中间节点 2.链表中倒数第k个节点  思路1:遍历链表,统计节点个数count,返回第count/2 +1个节点  📖Note: 注意循环条件为--mid,--mid循环执行mid-1次,mid--循环mid次,返回的是中间节点的下一个节点 思路二:快慢指针 设置一个慢指针slow,一个快指针fast,慢指针一

    2024年02月15日
    浏览(34)
  • LC-链表的中间节点(双指针)

    链接:https://leetcode.cn/problems/middle-of-the-linked-list/description/ 描述:给你单链表的头结点 head ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 输入:head = [1,2,3,4,5] 输出:[3,4,5] 解释:链表只有一个中间结点,值为 3 。 输入:head = [1,2,3,4,5,6

    2024年02月12日
    浏览(46)
  • 【Leetcode】移除链表元素 链表的中间节点 链表中倒数第k个节点

    目录 一.【Leetcode203】移除链表元素 1.链接 2.题目再现  A.双指针法 B.类尾删法 C.哨兵位 二.【Leetcode876】链表的中间节点 1.链接:链表的中间节点 2.题目再现 3.解法:快慢指针 三.链表中倒数第k个节点 1.链接:链表中倒数第k个节点 2.题目再现 3.解法 :快慢指针 1.链接 移除链表

    2024年02月01日
    浏览(64)
  • 【C语言】Leetcode 876. 链表的中间节点

    主页:17_Kevin-CSDN博客 专栏:《Leetcode》  通过题目的要求可以判断出有两种示例要解决,一种是偶数节点的链表,一种是奇数节点的链表,应对这两种情况我们需要使程序对二者都可以兼容。 中间节点,只要找到中间的位置就能找到中间的节点。那么这个位置要怎么去查找

    2024年03月14日
    浏览(45)
  • 【数据结构和算法】删除链表的中间节点

    Java基础合集 数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 三、代码 四、复杂度分析 这是力扣的 2095 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。 慢慢开始链表的模块了

    2024年01月19日
    浏览(76)
  • 力扣2095.删除链表的中间节点(java快慢指针)

    Problem: 2095. 删除链表的中间节点 利用快慢指针,快指针每次走两步,慢指针每次走一步(循环退出条件是fast指针不为空同时fast.next不为空),但是我们容易发现这样到最后slow指针正好指向我们需要删除的节点,由于没有前指针,这样我们不便操作。此时可以借助虚拟头节点

    2024年02月06日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包