分割链表和回文链表习题

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

个人主页LaNzikinh-CSDN博客

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


一.回文链表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]

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

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

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;

}

相关推荐

  1. leetcode-

    2024-04-25 22:44:06       38 阅读
  2. 234.

    2024-04-25 22:44:06       16 阅读
  3. 234.

    2024-04-25 22:44:06       9 阅读
  4. 234.

    2024-04-25 22:44:06       7 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-04-25 22:44:06       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-04-25 22:44:06       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-04-25 22:44:06       18 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-04-25 22:44:06       20 阅读

热门阅读

  1. 玩转nginx的配置文件2

    2024-04-25 22:44:06       11 阅读
  2. 字符串、数组的反转

    2024-04-25 22:44:06       10 阅读
  3. SAP fiori 第三方网页认证登录(伪)

    2024-04-25 22:44:06       15 阅读
  4. 初识计算机网络

    2024-04-25 22:44:06       12 阅读
  5. LINUX如何 部署ansible

    2024-04-25 22:44:06       13 阅读
  6. python之schedule

    2024-04-25 22:44:06       11 阅读
  7. 什么是layer1,layer2,为什么区块链需要layer2?

    2024-04-25 22:44:06       10 阅读
  8. python-基础(4)-list

    2024-04-25 22:44:06       11 阅读
  9. TypeScript 泛型类型

    2024-04-25 22:44:06       12 阅读
  10. 鸿蒙应用开发之Web组件4

    2024-04-25 22:44:06       13 阅读