感谢大佬的光临各位,希望和大家一起进步,望得到你的三连,互三支持,一起进步
个人主页: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
但是注意!!!存在问题,因为之前可能已经有连好的存在,所以最后还要解开
文章来源地址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模板网!