感谢大佬的光临各位，希望和大家一起进步，望得到你的三连，互三支持，一起进步
个人主页：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]
思路：开哨兵为的头节点，搞两个链表在合并
但是注意！！！存在问题，因为之前可能已经有连好的存在，所以最后还要解开
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;
}
好文阅读
您阅读本篇文章共花了：
发表评论