分割链表和回文链表习题

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

分割链表和回文链表习题,链表,数据结构

感谢大佬的光临各位,希望和大家一起进步,望得到你的三连,互三支持,一起进步

个人主页:LaNzikinh-CSDN博客

收入专栏:初阶数据结构_LaNzikinh篮子的博客-CSDN博客

文章目录

 一.回文链表LCR 027. 回文链表 - 力扣(LeetCode)

 二.分割链表面试题 02.04. 分割链表 - 力扣(LeetCode)


一.回文链表LCR 027. 回文链表 - 力扣(LeetCode)

给定一个链表的 头节点 head ,请判断其是否为回文链表。

如果一个链表是回文,那么链表节点序列从前往后看和从后往前看是相同的。

示例 1:

分割链表和回文链表习题,链表,数据结构

输入: head = [1,2,3,3,2,1]输出: true

示例 2:

分割链表和回文链表习题,链表,数据结构

输入: head = [1,2]输出: false

思路:先找到中间结点,然后逆置,逆置完后在进行比较,比较完后如果一直相等,那就正确,不相等那就错误奇数偶数一样

偶数

分割链表和回文链表习题,链表,数据结构

奇数

分割链表和回文链表习题,链表,数据结构

之前写过一个反转链表的代码http://t.csdnimg.cn/tcPai,这次就来教一下如何求链表的中间节点,就是快慢指针的思想,快的走两步,慢的走一步

struct ListNode*mid(struct ListNode*head)
{
struct ListNode*slow.*fast;
slow=fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}

实现

bool isPalindrome(struct ListNode* head) 
{
	//求中间结点
	struct ListNode* mid = midd(head);
	//中间结点逆置
	struct ListNode* rhead = rereverList(mid);
	//两个链表判断
	struct ListNode* curA = head;
	struct ListNode* curB = rhead;
	//一个结束就停止循环
	while (curA && curB)
	{
		//不相等就停
		if (curA->val != curB->val)
			return false;
		//相等就继续走
		else
		{
			curA = curA->next;
			curB = curB->next;
		}
	}
	return true;
}

二.分割链表面试题 02.04. 分割链表 - 力扣(LeetCode)

给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

示例 1:

分割链表和回文链表习题,链表,数据结构

输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]

示例 2:

输入:head = [2,1], x = 2
输出:[1,2]

思路:开哨兵为的头节点,搞两个链表在合并

分割链表和回文链表习题,链表,数据结构

分割链表和回文链表习题,链表,数据结构

但是注意!!!存在问题,因为之前可能已经有连好的存在,所以最后还要解开

分割链表和回文链表习题,链表,数据结构文章来源地址https://www.toymoban.com/news/detail-861435.html

struct ListNode* partition(struct ListNode* head, int x)
{
	struct ListNode* LessHead, * LessTail, * greaterHead, * greatertail;
	//开辟哨兵位的头结点
	LessHead = LessTail = (struct ListNode*)malloc(sizeof(struct ListNode*));
	greaterHead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode*));
	LessTail->next = NULL;
	greatertail->next = NULL;
	struct ListNode* cur = head;
	//当cur走完,循环停止
	while (cur)
	{
		//如果小,放入less链表中
		if (cur->val < x)
		{
			LessTail->next = cur;
			LessTail = cur;
		}
		//如果大于等于,放入greater链表中
		else
		{
			greatertail->next = cur;
			greatertail = cur;
		}
		cur = cur->next;
	}
	//最后把链表合并
	LessTail->next = greaterHead->next;
	//解开已经有连好的存在
	greatertail = NULL;
	//存储哨兵位前的元素,释放哨兵位的头结点
	struct ListNode* newhead = LessHead->next;
	free(LessHead);
	free(greaterHead);
	return newhead;

}

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

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

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

相关文章

  • 数据结构顺序表和链表(超详细)

    线性表 ( linear list ) 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构, 常见的线性表:顺序表、链表、栈、队列、字符串 ... 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的, 线性表在

    2024年02月13日
    浏览(51)
  • 数据结构:队列(链表和数组模拟实现)

    目录 1.何为队列 2.链表模拟实现 2.1 节点和队列创建 2.2 初始化队列 2.3 入队操作 2.4 出队操作 2.5 遍历队列 2.6 获取队首和队尾元素 2.7 判断队列是否为空 2.8 完整实现 3. 数组模拟实现 3.1 创建队列 3.2 入队和出队操作 3.3 遍历队列 3.4 获取队首和队尾元素  3.5 判断队列是否为空

    2024年02月03日
    浏览(52)
  • 【数据结构】链表的回文结构

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

    2024年02月12日
    浏览(53)
  • 【手撕数据结构】(三)顺序表和链表

    🎗️线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 🎗️线性表在逻辑上是线性结构,也就说是一条连续的直线。但是在物理结构上并不一定是连续的,线性表在物理上存储

    2024年02月05日
    浏览(50)
  • 数据结构奇妙旅程之顺序表和链表

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年02月05日
    浏览(60)
  • 【数据结构初阶】顺序表和链表(1)

    线性表(linear list) 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上

    2024年02月08日
    浏览(194)
  • 【数据结构】认识链表和模拟实现单链表

    即使骑的小电驴,也要奋力前进 目录 1.链表 1.1 链表的概念  1.2 链表的逻辑结构图和物理结构图 1.2.1 链表的逻辑结构图  1.2.2 链表的物理结构图  1.3链表结构的分类 1.3.1 链表通过什么进行结构的分类  1.3.2 不同链表结构的逻辑图 2.模拟实现一个单向链表  2.1 MyLinkedList类的

    2024年02月14日
    浏览(55)
  • 数据结构修炼第二篇:顺序表和链表

    第一章 时间复杂度和空间复杂度 第二章 顺序表,列表 第三章 栈和队列 第四章 二叉树 第五章 排序 作者:🎈乐言🎈 简介:🎈大一学生,目前在致力于c/c++/python,高数的学习,有问题尽管问我,关注后私聊! 持续更新专栏:《c进阶》,《数据结构修炼》 🚀 (优质好文持

    2024年02月02日
    浏览(101)
  • 【数据结构篇C++实现】- 线性表 - 顺序表和链表

    友情链接:C/C++系列系统学习目录 故事导入: 幼儿园放学时,一个班级的小朋友,一个跟着一个排队出校,有一个打头,有一个收尾,当中的小朋友每一个都知道他前面和后面的一个是谁,就如同一根线把他们串联了起来。如此具有像线一样的性质的表就叫线性表 线性表(

    2024年02月07日
    浏览(54)
  • 初阶数据结构之---顺序表和链表(C语言)

    线性表: 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构,也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上存储时,通常以 数组 和 链式结构 的形式存储。

    2024年02月22日
    浏览(61)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包